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

题目描述

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

如果数组中不存在target，返回：

[-1, -1]

要求算法的时间复杂度为：

O(log n)

示例：

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

一、为什么使用二分查找？

题目给出了两个重要条件：

1. 数组按照非递减顺序排列
2. 要求时间复杂度为O(log n)

有序数组具备单调性，因此可以使用二分查找。

普通遍历最坏需要检查数组中的所有元素，时间复杂度为：

O(n)

二分查找每次可以排除一半搜索范围，时间复杂度为：

O(log n)

例如，当数组长度为1024时：

1024 → 512 → 256 → 128 → ... → 2 → 1

最多只需要大约10次查找，因为：

2¹⁰ = 1024

二、普通二分查找为什么不够？

普通二分查找只负责寻找任意一个等于target的元素。

例如：

nums = [5, 7, 7, 8, 8, 10] target = 8

普通二分查找可能找到下标3，也可能找到下标4。

但题目要求返回完整区间：

[3, 4]

因此需要进行两次二分查找：

1. 寻找第一个大于等于target的位置
2. 寻找第一个严格大于target的位置

设这两个位置分别为：

lower_bound upper_bound

那么目标值的范围就是：

[lower_bound, upper_bound - 1]

三、左闭右开区间

本文采用左闭右开的搜索区间：

[left, right)

其中：

• left对应的位置包含在搜索范围内
• right对应的位置不包含在搜索范围内

初始化：

left=0right=len(nums)

这样[0, len(nums))正好覆盖整个数组。

循环条件为：

whileleft<right:

当循环结束时：

left == right

此时left和right指向最终的边界位置。

四、寻找左边界

左边界可以定义为：

数组中第一个大于等于target的位置。

也就是寻找第一个满足以下条件的位置：

nums[i] >= target

情况一：nums[mid] < target

如果：

nums[mid]<target

由于数组已经有序，mid及其左边的元素都不可能成为答案。

因此将左边界更新为：

left=mid+1

情况二：nums[mid] >= target

如果：

nums[mid]>=target

说明mid可能是答案，但左边还可能存在更靠前的合法位置。

因此保留mid，继续向左收缩：

right=mid

代码实现

deflower_bound(nums,target):left=0right=len(nums)whileleft<right:mid=left+(right-left)//2ifnums[mid]<target:left=mid+1else:right=midreturnleft

五、手动执行左边界查找

对于：

nums = [5, 7, 7, 8, 8, 10] target = 8

初始状态：

left = 0 right = 6

第一轮

mid = 0 + (6 - 0) // 2 = 3 nums[mid] = 8

因为：

nums[mid] >= target

执行：

right=mid

更新后：

left = 0 right = 3

第二轮

mid = 0 + (3 - 0) // 2 = 1 nums[mid] = 7

因为：

nums[mid] < target

执行：

left=mid+1

更新后：

left = 2 right = 3

第三轮

mid = 2 + (3 - 2) // 2 = 2 nums[mid] = 7

执行：

left=mid+1

更新后：

left = 3 right = 3

此时left < right不成立，循环结束，返回：

3

所以第一个大于等于8的位置是下标3。

六、寻找右边界

为了确定最后一个target的位置，可以先寻找：

第一个严格大于target的位置。

也就是寻找第一个满足以下条件的位置：

nums[i] > target

如果：

nums[mid]<=target

说明mid不是第一个大于target的位置，需要继续向右寻找：

left=mid+1

否则：

nums[mid]>target

说明mid可能是答案，需要保留mid并继续向左寻找：

right=mid

代码如下：

defupper_bound(nums,target):left=0right=len(nums)whileleft<right:mid=left+(right-left)//2ifnums[mid]<=target:left=mid+1else:right=midreturnleft

upper_bound返回第一个大于target的位置，因此最后一个等于target的位置为：

upper_bound(nums,target)-1

七、两种边界的关键区别

寻找左边界时：

ifnums[mid]<target:left=mid+1else:right=mid

寻找第一个大于目标值的位置时：

ifnums[mid]<=target:left=mid+1else:right=mid

二者的区别只有一个等号：

lower_bound：nums[mid] < target upper_bound：nums[mid] <= target

当nums[mid] == target时：

• 寻找左边界：继续向左寻找
• 寻找右边界：继续向右寻找

可以记忆为：

找左边界，相等时向左； 找右边界，相等时向右。

八、如何判断目标值不存在？

lower_bound找到的是第一个大于等于target的位置，但这个位置上的元素不一定等于target。

例如：

nums = [5, 7, 7, 8, 8, 10] target = 6

第一个大于等于6的元素是7，其下标为1。

因此，还需要检查：

nums[start]==target

另外，如果所有元素都小于target，lower_bound会返回：

len(nums)

例如：

nums = [5, 7, 8] target = 10

查找结果为：

start = 3 len(nums) = 3

因此目标值不存在的完整判断是：

ifstart==len(nums)ornums[start]!=target:return[-1,-1]

九、为什么必须先判断数组越界？

下面的判断顺序是安全的：

ifstart==len(nums)ornums[start]!=target:

Python 的or具有短路特性。

当：

start==len(nums)

为真时，Python 不会继续执行：

nums[start]

因此不会发生数组越界。

如果把条件反过来：

ifnums[start]!=targetorstart==len(nums):

当start == len(nums)时，程序会先访问不存在的下标，从而抛出：

IndexError: list index out of range

十、完整代码

classSolution:defsearchRange(self,nums:list[int],target:int)->list[int]:deflower_bound():"""寻找第一个大于等于 target 的位置。"""left=0right=len(nums)whileleft<right:mid=left+(right-left)//2ifnums[mid]<target:left=mid+1else:right=midreturnleftdefupper_bound():"""寻找第一个严格大于 target 的位置。"""left=0right=len(nums)whileleft<right:mid=left+(right-left)//2ifnums[mid]<=target:left=mid+1else:right=midreturnleft start=lower_bound()ifstart==len(nums)ornums[start]!=target:return[-1,-1]end=upper_bound()-1return[start,end]

十一、使用通用函数简化代码

也可以将两个二分查找统一为一个通用函数：

classSolution:defsearchRange(self,nums:list[int],target:int)->list[int]:deflower_bound(value):left=0right=len(nums)whileleft<right:mid=left+(right-left)//2ifnums[mid]<value:left=mid+1else:right=midreturnleft start=lower_bound(target)ifstart==len(nums)ornums[start]!=target:return[-1,-1]end=lower_bound(target+1)-1return[start,end]

这里：

lower_bound(target)

寻找第一个大于等于target的位置。

而：

lower_bound(target + 1)

对于整数数组而言，相当于寻找第一个大于target的位置。

需要注意：在具有固定整数范围的语言中，target + 1可能溢出。分别实现lower_bound和upper_bound会更加通用。

十二、复杂度分析

进行了两次二分查找，每次时间复杂度为：

O(log n)

因此总时间复杂度仍然是：

O(log n)

算法只使用了固定数量的变量，空间复杂度为：

O(1)

十三、容易犯的错误

1. 找到目标值后立即返回

ifnums[mid]==target:returnmid

这样只能找到任意一个目标值，不能保证找到左右边界。

2. 相等时更新方向错误

寻找左边界时，相等应该向左收缩：

right=mid

寻找右边界时，相等应该继续向右：

left=mid+1

3. 混用区间定义

如果采用左闭右开区间[left, right)，就应该保持：

right=len(nums)whileleft<right:

不要随意和闭区间[left, right]的写法混用。

4. 返回mid

循环结束后应该返回：

left

或者：

right

不能返回mid。因为mid只是最后一次检查的位置；当数组为空时，mid甚至没有被定义。

5. 忘记判断目标值是否存在

lower_bound找到的是第一个大于等于目标值的位置，不保证该位置的元素一定等于目标值。

必须检查：

start==len(nums)ornums[start]!=target

十四、二分查找的本质

二分查找不只是“在有序数组中寻找某个数”。

它更一般的用途是：

在一个具有单调性的搜索空间中，寻找分界点。

本题存在两个分界点：

小于 target | 大于等于 target

以及：

小于等于 target | 大于 target

通过两次二分查找确定这两个分界点，就能得到目标值的完整区间。

最终关系为：

开始位置 = 第一个大于等于 target 的位置 结束位置 = 第一个大于 target 的位置 - 1