距离上次更新已经过去了 2013 天,文章内容可能已经过时。
题目
给定一个按照升序排列的整数数组 nums
,和一个目标值 target
。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n)
级别。
如果数组中不存在目标值,返回 [-1, -1]
。
示例 1:
Code
1 | 输入: nums = [5,7,7,8,8,10], target = 8 |
示例 2:
Code
1 | 输入: nums = [5,7,7,8,8,10], target = 6 |
题解
思路
- 看到这道题很容易想到使用二分查找
- 但是难点在于,不仅要找到这个值的下标,还要找起始下标和终结下标
- 其实单纯使用两个二分查找即可,一个找起始下标,一个找最终下标
- 你可能会疑惑,这样会不会造成太多冗余计算?
- 但实际上,
O(logn)
和O(2logn)
是相等的,都是O(logn)
的时间复杂度。 - 所以使用两次二分查找的方式可以减少你的思考方式,同时不会增加复杂度。
二分查找细节
- 首先初始化l,r,左右指针
- 循环条件设为当l<r,这样设立的原因是跳出循环的时候l与r总是相等的,不用思考是l还是r
- 取中值,取中左还是中右,这就需要看情况了。
- 如果我们想要找值的起始下标,那么当mid对应值大于这个值或者哪怕当找到这个值的时候,右边界都要缩小
- 即当
nums[mid] >= target
的时候,r = mid
- 同时要注意不能以mid-1这样的形式缩小,否则当找到这个起始下标的时候还得再减1,就不对了。
- 因为不可以左右两个都=mid,必须有一个=mid+1,否则会陷入死循环。
- 所以在其他情况下,左边界等于mid + 1
- 同时,mid取左中还是右中,要以你选择哪个是mid+1来定。这里我们选了mid+1的是左边,所以我们要取左中值。否则会陷入死循环。
- 所以可以这样写出代码
python
1 | while l < r: |
- 对于取结束下标,也是如此。
代码
python
1 | class Solution: |