一、题目描述

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

如果数组中不存在target，返回[-1,-1]。题目要求算法的时间复杂度必须为O(log n)。

例如：

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

数字8出现了两次，第一次出现的位置是下标3，最后一次出现的位置是下标4。

如果目标值为6，数组中不存在该数字，则返回：

[-1,-1]

数组已经有序，并且时间复杂度要求为O(log n)，因此这道题应该使用二分查找。问题在于：普通二分查找只能找到目标值的某一个位置，如何进一步找到它的左右边界？

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

标准二分查找在发现nums[mid] == target时会立即返回mid：

if (nums[mid] == target) { return mid; }

但是，当数组中存在多个相同元素时，这个mid不一定是第一个位置，也不一定是最后一个位置。

例如：

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

二分查找可能先找到下标4，但我们还不能确定下标3是否也是8。同理，即使第一次找到的是下标3，也不能确定它右侧是否还有目标值。

因此，本题找到target后不能立即返回，而是应该：

1. 先记录当前找到的下标；

2. 根据要查找的边界，继续向左或向右搜索；

3. 直到搜索区间为空，最后一次记录的位置就是对应边界。

三、整体思路：执行两次二分查找

目标值的开始位置和结束位置是两个不同的问题，可以分别执行一次二分查找：

• 第一次查找左边界，即目标值第一次出现的位置；

• 第二次查找右边界，即目标值最后一次出现的位置。

两个搜索过程的大部分逻辑完全相同，只有在命中目标值后的搜索方向不同。因此，可以编写一个findMost方法，并通过布尔参数isLeft区分搜索目标：

findMost(nums, target, true); // 查找左边界 findMost(nums, target, false); // 查找右边界

最终将两次搜索的结果组合起来：

return new int[] { findMost(nums, target, true), findMost(nums, target, false) };

如果目标值不存在，两次搜索都会返回初始值-1，自然得到[-1,-1]。

四、tempIndex为什么必不可少

在二分查找中定义一个临时变量：

int tempIndex = -1;

每当发现nums[mid] == target时，就把当前下标记录下来：

tempIndex = mid;

之所以只记录而不立即返回，是因为当前的mid只是一个候选边界，真正的左边界可能还在左侧，真正的右边界也可能还在右侧。

如果后续搜索又找到了更靠近目标方向的相同元素，就再次更新tempIndex。当循环结束时，tempIndex保存的就是最终边界。

如果整个搜索过程中一次都没有找到target，tempIndex会保持为-1。

五、如何查找左边界

查找左边界时，遇到nums[mid] == target，说明当前下标可能是第一个位置，但它的左边仍可能存在相同元素。

因此先记录当前位置，再继续搜索左半部分：

tempIndex = mid; right = mid - 1;

例如：

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

如果当前找到下标4，先把4记录下来，然后将右边界移动到3，继续检查左侧。若之后发现下标3也是8，就用3更新tempIndex。

循环结束后，得到左边界3。

可以把查找左边界的规则记为：

命中后记录答案，并继续向左搜索。

六、如何查找右边界

查找右边界的逻辑与左边界相反。

当nums[mid] == target时，当前下标可能是最后一个位置，但右侧仍可能存在相同元素。因此先记录当前位置，再继续搜索右半部分：

tempIndex = mid; left = mid + 1;

如果当前先找到下标3，就将3记录下来，然后继续搜索它的右侧。后续找到下标4时，再将tempIndex更新为4。

循环结束后，得到右边界4。

对应的记忆规则是：

命中后记录答案，并继续向右搜索。

七、未命中时如何更新区间

除了命中目标值后的特殊处理，其余情况与标准二分查找完全相同。

如果中间元素小于目标值，目标值只能出现在右侧：

if (nums[mid] < target) { left = mid + 1; }

如果中间元素大于目标值，目标值只能出现在左侧：

else if (nums[mid] > target) { right = mid - 1; }

只有在nums[mid] == target时，才需要根据isLeft决定继续搜索的方向。

八、完整 Java 代码

下面的代码严格使用同一个findMost方法完成左右边界查找：

class Solution { public int[] searchRange(int[] nums, int target) { return new int[] { findMost(nums, target, true), findMost(nums, target, false) }; } // isLeft 为 true 时查找左边界，否则查找右边界 private int findMost(int[] nums, int target, boolean isLeft) { int left = 0; int right = nums.length - 1; int tempIndex = -1; while (left <= right) { int mid = left + ((right - left) >>> 1); if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else { // 先记录当前命中的位置 tempIndex = mid; if (isLeft) { // 查找左边界：继续向左搜索 right = mid - 1; } else { // 查找右边界：继续向右搜索 left = mid + 1; } } } return tempIndex; } }

这里使用下面的方式计算中间下标：

int mid = left + ((right - left) >>> 1);

它与(left + right) / 2的作用相同，但可以避免left + right过大时出现整数溢出。

九、示例推演

以nums = [5,7,7,8,8,10]、target = 8为例。

1. 查找左边界

初始区间为[0,5]：

mid = 2，nums[2] = 7 < 8 left = 3

搜索区间变为[3,5]：

mid = 4，nums[4] = 8 tempIndex = 4 right = 3

由于查找左边界，命中后继续向左。此时区间为[3,3]：

mid = 3，nums[3] = 8 tempIndex = 3 right = 2

循环结束，左边界为3。

2. 查找右边界

前两步同样会找到下标4：

tempIndex = 4 left = 5

因为查找右边界，命中后继续向右。接下来nums[5] = 10 > 8，搜索结束，右边界为4。

最终返回：

[3,4]

十、复杂度分析

查找左边界和右边界分别执行一次二分查找，每次的时间复杂度都是O(log n)。两次相加仍然是：

O(log n)

算法只使用了left、right、mid和tempIndex等变量，没有创建与数组长度相关的额外空间，因此空间复杂度为：

O(1)

十一、常见错误

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

这样只能得到目标值的任意一个位置，无法保证它是左边界或右边界。

2. 命中后没有保存当前位置

继续搜索可能会导致最终区间为空，因此必须先使用tempIndex保存当前候选答案。

3. 左右边界的搜索方向写反

查找左边界时应执行right = mid - 1；查找右边界时应执行left = mid + 1。

4. 使用线性扫描寻找边界

先二分找到目标值，再向左右逐个扫描，最坏情况下需要遍历整个数组，时间复杂度会退化为O(n)，不符合题目要求。

5. 使用left < right配合闭区间边界

本文采用闭区间[left,right]，因此循环条件必须是left <= right。如果混用不同二分模板，容易漏掉只剩一个元素的情况。

十二、总结

这道题是在标准二分查找基础上增加了“边界搜索”。由于数组中可能出现多个连续的目标值，命中目标值后不能立即返回，而要记录当前位置并继续向对应方向搜索。

为了避免编写两套重复代码，可以通过isLeft参数复用一个findMost方法：isLeft为true时继续向左收缩，寻找第一次出现的位置；为false时继续向右收缩，寻找最后一次出现的位置。