排序数组查找元素第一个和最后一个
原题
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
题目解析
这一题目是一个典型的二分查找，不过考察的细节更多，需要对于二分查找有一个比较深入的理解。
题目的核心问题：对于一个元素，找到其在数列中的开始和结束位置。这一问题可以转化为，找到第一个target和第一个大于target的元素。此时我们发现，传统的二分查找并不能解决这一问题(因为不确定找到的target值到底是不是数列中的首个该元素)。暴力的方法会想到先二分查找到这个元素然后从这个下标开始向前向后搜索，但显然这样复杂度太高，退化成了$O(n)$。
当然，golang中本身提供了这样的接口：
// 返回第一个>= target的值
pos := sort.SearchInts(nums, target)
//因此直接调库的话就是
lpos := sort.SearchInts(nums, target)
if lpos == len(nums) || nums[lpos] != target {
return []int{-1, -1}
}
rpos := sort.SearchInts(nums, target + 1) - 1
return []int{lpos, rpos}
关于该函数的更多信息可以看这个博客。
但显然我们不满足于直接调库，而是希望能够具体来实现。
与传统的二分查找相比，这里的核心在于nums[mid]==target时应该如何处理？如果想要找到第一个元素，显然不能简单的在这个条件下return mid。于是我们想到，可以在每次出现nums[mid]==target时将这个mid记录下来，然后让下一次的二分区间不包括mid。通过在更新r的条件下额外记录一下mid，就实现了不断在记录该元素的一个具有向左趋势的下标。通过这样的方式我们就解决了找到第一个target的任务。
那么对于第一个大于target的元素怎么办呢？很简单，找到第一个大于等于target+1的位置rpos，然后rpos--就好了。
因此该题能以如下的方式解决:
func binarySearch(nums []int, target int) (ans int) {
l := 0
r := len(nums) - 1
ans = len(nums) // *注意点1
for l <= r {
mid := (l+r) >> 1
if nums[mid] >= target {
r = mid - 1
ans = mid
} else {
l = mid+1
}
}
return
}
func searchRange(nums []int, target int) []int {
lIndex := binarySearch(nums, target)
rIndex := binarySearch(nums, target+1)
rIndex--
if lIndex <= rIndex && rIndex < len(nums) && nums[lIndex] == target && nums[rIndex] == target { // *注意点2
return []int{lIndex, rIndex}
} else {
return []int{-1, -1}
}
}
- 注意点1：这里一定要初始化
ans=len(nums)，因为如果找不到target或者target+1时，如果不初始化ans就会导致其返回0，然后导致错误的lIndex和rIndex判断(例如对于nums=[1] target=1时，不进行此初始化就会返回-1 -1) - 注意点2：这里要注意边界条件的判断要全面，首先要考虑两者的相对关系和是否越界然后再判断是不是都等于
target。
