题目描述
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
Follow up: Could you write an algorithm with O(log n) runtime complexity?
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
Constraints:
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is a non-decreasing array.
- -10^9 <= target <= 10^9
题目分析
问题要求在O(log n)时间复杂度内完成查找，那么二分查找自然被优先考虑。最朴素的想法就是通过二分查找找到target值，然后向左右两边去检测边界值。但这个方式在遇到 bad case时很容易退化为O(n)的复杂度，比如 1 2 2 2 2 …. 2 3这样一个数组，target为2，假设2的数量非常多，刚才这种方式就退化为了O(n)
为了避免进行这种范围检测，我们可以将这个问题转换成如下的问题：
- 如果我们能找出大于
target的第一个值；那么问题答案的右界我们就可以确定了； - 如果此时我们再找出大于
target-1的第一个值，并且该值等于target，那么问题的左界我们也可以确定
因此解法如下:
示例代码
// binary search + lower bound / upper bound
func searchRange(nums []int, target int) []int {
lbleft := lowerBound(nums, target-1)
// 不存在的case:
// case 1: 大于target的左界为 len(nums)，说明nums中所有值都小于target
// case 2: 大于target-1的第一个值不是target，说明target不存在
if lbleft == len(nums) || nums[lbleft] != target {
return []int{-1, -1}
}
ans := []int{lbleft}
// 再找到右界
lbright := lowerBound(nums, target)
// 如果走到这一步，说明左界已经找到了，target必然存在；不需要再判断右界的合法性了，直接append，返回结果即可
ans = append(ans, lbright-1)
return ans
}
// 二分查找大于target的第一个数的位置
func lowerBound(nums []int, target int) int {
// right初始化为数组长度；用右界去逼近target，最终找到第一个大于target的位置
left, right := 0, len(nums)
for {
if left >= right {
break
}
mid := left + (right-left)/2
if nums[mid] > target {
right = mid
continue
}
if nums[mid] <= target {
left = mid + 1
}
}
return right
}