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

2025/12/17 23:24:46 来源：https://blog.csdn.net/qq_32882309/article/details/143739911 浏览: 次关键词：LeetCode【0034】在排序数组中查找元素的第一个和最后一个位置

本文目录

1 中文题目
2 求解方法：左右边界二分查找
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
3 题目总结

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]

提示：

$\leq nums.length \leq10^5$
$-10^9 \leq nums[i] \leq 10^9$
nums 是一个非递减数组
$-10^9 \leq target \leq 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]