LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

// 方法1 双指针：不推荐// 时间复杂度：O(n)funcsearchRange(nums []int, targetint) []int {
// if len(nums) == 0 {//     return []int{-1, -1}// }left, right :=0, 0// 注意：要避免left和right越界for ; left<len(nums) &&nums[left] !=target; left++ {
    }
// 如果在nums中没找到target，则直接返回-1ifleft>=len(nums) {
return []int{-1, -1}
    }
// 注意：要避免left和right越界forright=left; right<len(nums) &&nums[right] ==target; right++ {
    }
right--// 因为最后right多加了一次，所以减回去return []int{left, right}
}
// 方法2 二分法 + 左右滑动指针：不推荐// 思路：如果在nums中找到了一个target，则继续在此基础上，通过左右滑动指针，来找到符合题意的区间// 平均时间复杂度：O(logn)，最坏情况下如果数组中的所有元素都一样，那最坏时间复杂度为O(n) funcsearchRange(nums []int, targetint) []int {
left, right :=0, len(nums) -1forleft<=right {
mid :=left+ (right-left) /2ifnums[mid] ==target {
// 找到target位置后，分别 向左/向右 寻找左右边界pre, end :=mid, midforpre>=0&&nums[pre] ==target {
pre--            }
forend<len(nums) &&nums[end] ==target {
end++            }
return []int{pre+1, end-1} // l在循环中多减了一次，要加回来；r在循环中多加了一次，要减回去       } elseifnums[mid] <target {
left=mid+1       } else {
right=mid-1       }
   }
return []int{-1, -1}
}
// 方法3 二分法：推荐// 思路：如果在nums中找到了一个target，则继续在此基础上用二分法分别查找左右边界，而不是用左右滑动指针来逐个遍历funcsearchRange(nums []int, targetint) []int {
return []int{ binarySearch(nums, target, true), binarySearch(nums, target, false) }
}
// leftOrRight为true找左边界，leftOrRight为false找右边界funcbinarySearch(nums []int, targetint, leftOrRightbool) int {
left, right, res :=0, len(nums) -1, -1forleft<=right {
mid :=left+ (right-left) /2iftarget==nums[mid] {
res=mid// 保存上一轮循环中target == nums[mid]时，对应的mid值// leftOrRight = true，继续寻找target的左边界，所以要缩小当前的右边界，right需要往左移ifleftOrRight {
right=mid-1// leftOrRight = false，继续寻找target的右边界，所以要扩大当前的右边界，left需要往右移            } else {
left=mid+1            }
        } elseiftarget>nums[mid] {
left=mid+1        } else { // target < nums[mid]right=mid-1        }
    }
returnres}