一、题目描述给定一个按照非递减顺序排列的整数数组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时会立即返回midif (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保存的就是最终边界。如果整个搜索过程中一次都没有找到targettempIndex会保持为-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 2nums[2] 7 8 left 3搜索区间变为[3,5]mid 4nums[4] 8 tempIndex 4 right 3由于查找左边界命中后继续向左。此时区间为[3,3]mid 3nums[3] 8 tempIndex 3 right 2循环结束左边界为3。2. 查找右边界前两步同样会找到下标4tempIndex 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时继续向右收缩寻找最后一次出现的位置。