34. 在排序数组中查找元素的第一个和最后一个位置

题目

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

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

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9

解答

思路

暴力做法就是从左到右遍历，时间复杂度为 $O (n)$ ，似乎可以过。

python

# 暴力做法
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        right = 0
        length = 0

        for i, x in enumerate(nums):
            if x == target:
                right = i
                length += 1
            elif x < target:
                continue
            else:
                break
        
        if length == 0:
            return [-1, -1]
        
        return [right - length + 1, right]

闭区间

暴力做法没有用到 数组是有序的 这一性质。我们用一组相向双指针 l = 0, r = n - 1，表示我们需要知道 nums[l..r] 这个 闭区间 内的每个数和 8 之间的大小关系。因此我们取 数组中间的数 mid = (l + r) / 2（下取整，相当于取了左边的数），无论它和 8 是什么关系，我们立刻可以知道数组中一般的元素和 8 之间的关系：

nums[mid] >= target 则 nums[mid..r] 都是 >= target 的
nums[mid] < target 则 nums[l..mid] 都是 < target 的
注意加法的溢出问题

之后的区间端点更新，要注意我们始终 在一个闭区间上做判断：

nums[mid..r] >= target 则更新没有确定区间的左半部分 r = mid - 1
nums[l..mid] < target 则更新没有确定区间的右半部分 l = mid + 1
防止 死循环：比如只有一个元素时，如果 l = mid 则没有任何变化

结束的时候：

结束就是区间上所有数字都判断完毕了，也就是待判断的闭区间为空 r < l
更新左端点之前一定有 nums[l..mid] < target，且更新为 l = mid + 1，因此 nums[l - 1] < target
更新右端点之前一定有 nums[mid..r] >= target，且更新为 r = mid - 1，因此 nums[r + 1] >= target

结束的时候 r + 1 一定满足要求，而 l - 1 一定不满足要求。循环结束时，一定有 r + 1 = l，因为循环结束之前闭区间一定 只有一个元素，此时 l = mid = r，然后再做一步判断就会得到 r + 1 = l：

nums[mid] >= target 则 r = mid - 1 = l - 1
nums[mid] < target 则 l = mid + 1 = r + 1
二者是一样的

所以满足要求的答案可以用 r + 1 或者 l 来表示。满足什么要求呢？也就是 nums[i] >= target，这样做就是找到了二者的分界线，自然也就是第一个 nums[i] >= target，也就是起始点。

如果没有满足要求的数，那么 l 会一直向右移动，直到二者重合之后，l 还是继续向右移动，最后 l == nums.size() 结束。

左闭右开区间

如果我们不是在 [0, n - 1] 上判断，而是在 [0, n) 上进行判断：

nums[mid] < target，则 l = mid + 1
nums[mid] >= target，则 r = mid

最后当 l == r 时 [l, r) 就已经空了，根据 更新的方程，在任何时候 nums[r] 都是满足要求的，因此循环结束时返回 l, r 都可以。

开区间

改为 (0, n) 上进行判断：

nums[mid] < target，则 l = mid
nums[mid] >= target，则 r = mid

最后当 l + 1 == r 时，开区间 (l, r) 就不包含任何整数了，可以退出循环。根据循环不变式，在任何时候 nums[r] 都是满足要求的，nums[l] 都是不满足要求的。因此循环结束时返回 r 即可。

代码

Python 代码

python

def lower_bound(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1     # 闭区间 [left, right]

    while left <= right:      # 区间不为空
        mid = (left + right) // 2
        
        if nums[mid] < target:
            left = mid + 1    # [mid + 1, right]
        else:
            right = mid - 1   # [left, mid - 1]
        
    return left # right + 1

def lower_bound2(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)         # 左闭右开区间 [left, right)

    while left < right:       # 区间不为空
        mid = (left + right) // 2
        
        if nums[mid] < target:
            left = mid + 1    # [mid + 1, right)
        else:
            right = mid       # [left, mid)
        
    return left  # right

def lower_bound3(nums: List[int], target: int) -> int:
    left = -1
    right = len(nums)         # 开区间 (left, right)

    while left + 1 < right:   # 区间不为空
        mid = (left + right) // 2
        
        if nums[mid] < target:
            left = mid        # (mid, right)
        else:
            right = mid       # (left, mid)
        
    return right # left + 1

总结：用到就是 循环不变式，保证在循环操作结束后 nums[l..r] 依然保持循环之前的性质。

二分查找还有四种类型：>=, >, <, <=，其中：

> x 就等价于 >= x + 1
< x 就等价于 >= x 的 左边那个数
<= x 就等价于 > x 的 左边那个数

因此最终代码为：

python

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = lower_bound(nums, target)

        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        
        end = lower_bound(nums, target + 1) - 1

        return [start, end]

时间复杂度就取决于 lower_bound() 的时间复杂度：由于每次都去掉了一半的元素，因此只需要操作 $\log n$ 次，因此：

时间复杂度为 $O (\log n)$
空间复杂度为 $O (1)$

C++ 代码

cpp

class Solution {
public:
    int lower_bound(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        return left;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);

        if (start == nums.size() || nums[start] != target) {
            return {-1, -1};
        }

        int end = lower_bound(nums, target + 1) - 1;

        return {start, end};
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置 ​

题目 ​

解答 ​

思路 ​

代码 ​

34. 在排序数组中查找元素的第一个和最后一个位置

题目

解答

思路

代码