Given an array of integers nums
sorted in ascending order, find the starting and ending position of a given target
value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1]
.
Example 1:
1 2
| Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
|
Example 2:
1 2
| Input: nums = [5,7,7,8,8,10], target = 6 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
这道题依然是二分查找的变体,最直接的思路就是先用二分查找找到 target 的位置,然后分别向左右扩展。这种方法不符合复杂度要求,不过却比较容易理解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| def search_range(nums: List[int], target: int) -> List[int]: l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) // 1 if nums[mid] == target: start, end = mid, mid while start >=0 and nums[start] == target: start -= 1 while end <= len(nums) - 1 and nums[end] == target: end += 1 return [start+1, end-1] else: if nums[mid] > target: r = mid - 1 else: l = mid + 1 return [-1, -1]
|
这里有两个点需要注意:
- 找到 target 再开始遍历时,要遍历到顶端的位置
- 返回的时候 start 要加 1 end 要减 1,因为 while 循环最后多一次操作
显然,这个复杂度是 O(n) 的,和从头到尾遍历可以说也没啥大的区别了。要达到题目要求的复杂度就只能另辟蹊径了。
我们再想想,因为数组是有序的,那是不是可以用两次二分查找,分别找到左边的 target 和右边的 target 呢?当然可以!只要改一下每次的条件,将等于 target 的跳过即可:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| def search_left(nums: list, target: int): l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) // 2 if nums[mid] >= target: r = mid - 1 else: l = mid + 1 return l
def search_right(nums: list, target: int): l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) // 2 if nums[mid] <= target: l = mid + 1 else: r = mid - 1 return r
def search_range(nums: list, target: int): l = search_left(nums, target) r = search_right(nums, target) if 0 <= l <= r < len(nums): return [l, r] return [-1, -1]
|
上面的左右两个函数可以合并为一个,最终的代码为:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| def search(nums: list, target: int, left: bool): l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) // 2 if nums[mid] > target: r = mid - 1 elif nums[mid] < target: l = mid + 1 else: if left: r = mid - 1 else: l = mid + 1 if left: return l else: return r
def searchRange(nums: list, target: int): l = search(nums, target, True) r = search(nums, target, False) if 0 <= l <= r < len(nums): return [l, r] return [-1, -1]
|
看了下 Solution 的解法也是类似的,不过多做了一点优化,就是当求出 l
后,先判断是否超出 range 范围,或者所在位置的元素是否不等于 target,只要满足其一就直接返回兜底结果,这样就少计算了一次右边的情况。
总结一下可以发现其中的关键是逆向思维,也就是平时用二分查找是找那个要的 target,这里恰好是 “不要”,其实是找的 target 边上的那两个元素。算法真美妙。