【LeetCode 题解】算法：34.在排序数组中查找元素的第一个和最后一个位置

一、问题剖析

题目要求

给定一个非递减数组 nums 和一个目标值 target，需要找到：

• 目标值在数组中的起始位置

• 目标值在数组中的结束位置
  如果目标值不存在，返回 [-1, -1]

关键约束

• 时间复杂度必须为 O (log n)：排除线性扫描的可能

• 数组可能包含重复元素：需要处理多个相同元素的情况

• 数组可能为空或全为负数：需考虑边界条件

二、核心思路：两次二分查找

1. 常规二分查找的局限性

普通二分查找只能找到一个匹配的位置，但无法确定是否为第一个或最后一个出现的位置。例如，数组 [5,7,7,8,8,10] 中查找 8，常规二分可能返回索引 3 或 4。

2. 左右边界二分法

通过两次独立的二分查找分别确定：

• 左边界：第一个等于 target 的位置

• 右边界：最后一个等于 target 的位置

左边界查找逻辑

初始化 left=0, right=n-1
当 left <= right 时：mid = (left + right) / 2if nums[mid] >= target:right = mid - 1else:left = mid + 1
最终检查 nums[left] 是否等于 target

右边界查找逻辑

初始化 left=0, right=n-1
当 left <= right 时：mid = (left + right) / 2if nums[mid] <= target:left = mid + 1else:right = mid - 1
最终检查 nums[right] 是否等于 target

三、Java 代码实现

​
class Solution {public int[] searchRange(int[] nums, int target) {int left = findLeftBound(nums, target);int right = findRightBound(nums, target);if (left <= right && nums[left] == target) {return new int[]{left, right};}return new int[]{-1, -1};}private int findLeftBound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}return left;}private int findRightBound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid - 1;}}return right;}
}​

四、代码详细解析

1. 主方法 searchRange

• 调用两次二分查找：分别获取左边界和右边界

• 有效性验证：检查左边界是否在有效范围内且对应值等于目标值

2. 左边界查找 findLeftBound

• 调整条件：当 nums[mid] >= target 时，说明左边界可能在左侧

• 循环结束后：left 指向第一个大于等于 target 的位置

3. 右边界查找 findRightBound

• 调整条件：当 nums[mid] <= target 时，说明右边界可能在右侧

• 循环结束后：right 指向最后一个小于等于 target 的位置

五、复杂度分析

时间复杂度

• 两次二分查找：每次时间复杂度为 O (log n)

• 总时间复杂度：O(log n)

空间复杂度

• 常数额外空间：O(1)

六、测试用例验证

测试用例 1

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

• 左边界查找：最终 left=3

• 右边界查找：最终 right=4

• 输出：[3,4]

测试用例 2

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

• 左边界查找：最终 left=0（nums[0]=5 <6）

• 右边界查找：最终 right=-1

• 输出：[-1,-1]

测试用例 3

输入：nums = [], target = 0

• 左边界查找：返回 0

• 右边界查找：返回 -1

• 验证：0 > -1，返回 [-1,-1]

七、常见问题与优化

问题 1：为什么需要两次二分查找？

• 左边界：在找到第一个匹配点后，需要继续向左查找

• 右边界：在找到最后一个匹配点后，需要继续向右查找

问题 2：如何处理数组为空？

• 直接返回 [-1,-1]

优化点：合并两次查找

可以将两次查找合并为一次，但会降低代码可读性。建议保持两次独立查找，逻辑更清晰。

感谢各位的阅读，后续将持续给大家讲解力扣中的算法题和数据库题，如果觉得这篇内容对你有帮助，别忘了点赞和关注，后续还有更多精彩的算法解析与你分享！