题目

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

1
2
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

1
2
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

题解

思路

  • 看到这道题很容易想到使用二分查找
  • 但是难点在于，不仅要找到这个值的下标，还要找起始下标和终结下标
  • 其实单纯使用两个二分查找即可，一个找起始下标，一个找最终下标
  • 你可能会疑惑，这样会不会造成太多冗余计算？
  • 但实际上，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的是左边，所以我们要取左中值。否则会陷入死循环。
  • 所以可以这样写出代码
1
2
3
4
5
6
while l < r:
    mid = (l + r) // 2
    if nums[mid] >= target:
        r = mid
    else:
        l = mid + 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
25
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 取起始下标
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1

        # 没找到
        if not nums or nums[l] != target:
            return [-1,-1]
        
        # 取结束下标
        a, b = 0, len(nums) - 1
        while a < b:
            mid = (a + b) // 2 + 1
            if nums[mid] <= target:
                a = mid
            else:
                b = mid - 1
        
        return [l,a]