一、问题剖析
题目要求
给定一个非递减数组 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) / 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
最终检查 nums[left] 是否等于 target
右边界查找逻辑
初始化 left=0, right=n-1
当 left <= right 时：
mid = (left + right) / 2
if nums[mid] <= target:
left = mid + 1
else:
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]
优化点：合并两次查找
可以将两次查找合并为一次，但会降低代码可读性。建议保持两次独立查找，逻辑更清晰。
感谢各位的阅读，后续将持续给大家讲解力扣中的算法题和数据库题，如果觉得这篇内容对你有帮助，别忘了点赞和关注，后续还有更多精彩的算法解析与你分享！