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

1 中文题目

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

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

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

示例：

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

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

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

提示：

• $0\le nums.length\le 10^5$
• $-10^9\le nums[i]\le 10^9$
• nums 是一个非递减数组
• $-10^9\le target\le 10^9$

---

2 求解方法：左右边界二分查找

2.1 方法思路

方法核心

• 使用两次改进的二分查找
• 分别查找目标值的左右边界
• 通过不同的条件控制边界的移动

实现步骤

（1）查找左边界的过程：

• 初始化左右指针，分别指向数组的开始和结束
• 在循环中计算中间位置
• 当找到大于或等于目标值的元素时，记录该位置并继续往左找
• 当找到小于目标值的元素时，需要往右找
• 最终找到第一个等于目标值的位置
• 需要判断是否越界以及是否真的找到了目标值

（2）查找右边界的过程：

• 同样初始化左右指针
• 在循环中不断更新中间位置
• 当找到小于或等于目标值的元素时，继续往右找
• 当找到大于目标值的元素时，需要往左找
• 最终找到最后一个等于目标值的位置
• 同样需要进行边界检查

方法示例

输入：nums = [5,7,7,8,8,10], target = 8左边界查找过程：
1. 初始状态：left = 0, right = 5mid = 2, nums[mid] = 7 < targetleft = mid + 1 = 32. 第二次迭代：left = 3, right = 5mid = 4, nums[mid] = 8 == targetright = mid - 1 = 33. 第三次迭代：left = 3, right = 3mid = 3, nums[mid] = 8 == targetright = mid - 1 = 24. 循环结束：left = 3，找到左边界右边界查找过程：
1. 初始状态：left = 0, right = 5mid = 2, nums[mid] = 7 < targetleft = mid + 1 = 32. 第二次迭代：left = 3, right = 5mid = 4, nums[mid] = 8 == targetleft = mid + 1 = 53. 第三次迭代：left = 5, right = 5mid = 5, nums[mid] = 10 > targetright = mid - 1 = 44. 循环结束：right = 4，找到右边界返回：[3, 4]

2.2 Python代码

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def binary_search_left(nums, target):# 寻找左边界的二分查找left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2# 如果中间值大于或等于目标值，继续往左找if nums[mid] >= target:right = mid - 1# 如果中间值小于目标值，往右找else:left = mid + 1# 判断是否找到目标值if left >= len(nums) or nums[left] != target:return -1return leftdef binary_search_right(nums, target):# 寻找右边界的二分查找left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2# 如果中间值小于或等于目标值，继续往右找if nums[mid] <= target:left = mid + 1# 如果中间值大于目标值，往左找else:right = mid - 1# 判断是否找到目标值if right < 0 or nums[right] != target:return -1return right# 特殊情况处理if not nums:return [-1, -1]# 分别查找左右边界left_bound = binary_search_left(nums, target)right_bound = binary_search_right(nums, target)return [left_bound, right_bound]

2.3 复杂度分析

• 时间复杂度：O(log n)
  • 两次二分查找
  • 每次二分查找的时间复杂度为O(log n)
• 空间复杂度：O(1)
  • 只使用常数额外空间
  • 不随输入规模增长

---

3 题目总结

题目难度：中等
数据结构：数组
应用算法：左右边界二次二分查找