LeetCode 34：在排序数组中查找元素的首尾位置——Java 两次二分查找详解
一、题目描述
给定一个按照非递减顺序排列的整数数组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后不能立即返回，而是应该：
先记录当前找到的下标；
根据要查找的边界，继续向左或向右搜索；
直到搜索区间为空，最后一次记录的位置就是对应边界。
三、整体思路：执行两次二分查找
目标值的开始位置和结束位置是两个不同的问题，可以分别执行一次二分查找：
第一次查找左边界，即目标值第一次出现的位置；
第二次查找右边界，即目标值最后一次出现的位置。
两个搜索过程的大部分逻辑完全相同，只有在命中目标值后的搜索方向不同。因此，可以编写一个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时继续向右收缩，寻找最后一次出现的位置。