企业官网建设流程全解析

一句话说明核心方法

用左闭右开区间[left, right)的二分查找：每次取中点比较，target 更大就收缩左边界、更小就收缩右边界，循环结束时left的位置恰好是“找到的下标”或“应插入的位置”——本质就是求第一个大于等于 target 的下标(lower bound)。

思路推导

题意转化：在一个升序无重数组里，返回 target 的下标；不存在则返回“它插进去后数组依然有序”的位置。一句话：求第一个nums[i] >= target的 i。

关键观察 1:插入位置有四种情况，可以统一处理——

四种情况全部等价于“第一个 >= target 的下标”。如果每种情况分别写 if,代码会碎成一片；统一成 lower bound 语义，一份逻辑全覆盖。

关键观察 2:用左闭右开[left, right)而不是左闭右闭[left, right]——

• right = nums.length是合法的“虚拟插入点”(target 比谁都大时插到最后)，右开区间允许 right 取到这个位置；
• 判断“区间是否为空”只需left < right一个条件；左闭右闭要写left <= right,边界手误(漏等号)是二分最高频 bug;
• 收缩右边界写right = mid(mid 还可能是答案，不能扔)；左闭右闭则要right = mid - 1,一不注意就丢答案。

循环不变量：全程保持[0, left)内全小于 target,[right, n)内全大于等于 target。区间每轮严格缩小，空了(left == right)时，left左边全小、右边全大——它就是分界点，即插入位置。

二分过程示意(nums = [1,3,5,6], target = 2)

初始: left = 0, right = 4 区间 [0, 4) = {1, 3, 5, 6} 0 1 2 3 [ 1 3 5 6 ] L R 第1轮: mid = 0 + (4-0)/2 = 2 nums[2] = 5 > 2 → right = mid = 2 0 1 2 3 1 3 5 6 L R 区间缩小为 [0, 2) = {1, 3} 第2轮: mid = 0 + (2-0)/2 = 1 nums[1] = 3 > 2 → right = mid = 1 0 1 2 3 1 3 5 6 L R 区间缩小为 [0, 1) = {1} 第3轮: mid = 0 + (1-0)/2 = 0 nums[0] = 1 < 2 → left = mid + 1 = 1 0 1 2 3 1 3 5 6 L/R 区间为空,循环结束 返回 left = 1 ✓ (2 插在下标 1,数组变成 [1,2,3,5,6] 仍有序)

可以看到收敛的规律：大于 target 的元素不断被赶到右边(right = mid),小于 target 的不断被赶到左边(left = mid + 1),最后 left 正好夹在“全小的尾部”和“全大的头部”之间。

Java 完整代码

class Solution { public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length; // 右开:插入点可能是 n,所以取 length 而不是 length-1 while (left < right) { // 区间非空 [left, right) int mid = left + (right - left) / 2; // 防溢出写法 if (nums[mid] == target) { return mid; // 找到,直接返回 } else if (nums[mid] < target) { left = mid + 1; // mid 及其左边都 < target,整个丢弃 } else { right = mid; // nums[mid] > target,mid 可能是插入点,保留 } } // 走到这里说明 target 不存在,left 左边全 < target,右边全 > target return left; } }

关键代码逐行解释

• int right = nums.length——右开区间的初始化灵魂。target 比所有元素都大时要插在下标 n,如果初始化成nums.length - 1,这个答案就永远表达不出来，还得在结尾补特判。右开写法把“插入到最后”纳入了统一框架。

• while (left < right)——右开区间的空条件就是left == right,不带等号。对比左闭右闭的while (left <= right):一旦循环体里忘了配套的±1,右开写法最多漏解，左闭右闭会死循环(mid卡住不动)，后者更难排查。

• left + (right - left) / 2而不是(left + right) / 2——两者数学上等价，但当 left、right 都接近Integer.MAX_VALUE时，相加会整型溢出，相减不会。本题 n ≤ 10⁴ 溢不出来，但这是必须养成的肌肉记忆，大数组场景(如 300 最长递增子序列的二分)真的会炸。

• right = mid而不是right = mid - 1——因为nums[mid] > target时，mid 本身可能就是插入点(target 要插在 mid 这个位置)，把它扔掉就丢答案了。左开右开区间下 mid 始终是“待考察候选”，收缩但不排除。这是和左闭右闭写法(right = mid - 1)最容易搞混的一行。

• left = mid + 1——nums[mid] < target时，mid 位置的元素确定小于target,既不可能是答案下标，也不可能是插入点(mid 位置必然被更大的数占着)，可以放心丢弃。

• return left(而不是 right 或 mid)——循环结束时left == right,三者数值相同，但语义上left最贴切：它是循环不变量维护出来的“第一个 >= target 的下标”。mid此时是上一轮的残留值，虽然在数值上碰巧相等，但写mid会误导读者以为它还有意义。

时间、空间复杂度

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

  • 每轮循环区间至少缩小一半(要么left = mid + 1,要么right = mid,两种收缩都严格推进边界)，从 n 收敛到 1 最多 ⌈log₂ n⌉ 轮。n = 10⁴ 时约 14 轮。

• 空间复杂度：O(1)

  • 只用了 left / right / mid 三个变量，无递归、无辅助数组。

易错点

• right初始化成nums.length - 1却仍用右开逻辑：区间变成[0, n-1),漏掉了最后一个元素；更糟的是 target 大于所有元素时返回错位。初始化和循环条件、收缩方式是一个整体，要换就整套换(见模板中的左闭右闭变体)。

• right = mid - 1(把右开当成右闭写)：当nums[mid] > target且 mid 正好是插入点时，答案被扔掉，返回值偏小。判别方法：右开区间收缩永不出界(mid 始终 < right),写mid - 1就说明混用了两套约定。

• (left + right) / 2溢出隐患：本题数据范围安全，但这是二分模板的通用坑，面试官最爱问“这句还能怎么写”。固定用left + (right - left) / 2。

• 死循环：收缩条件不推进：如果小于分支写成left = mid,当区间只剩两个元素时 mid 永远等于 left,区间不再缩小，死循环。左边界收缩必须mid + 1(因为nums[mid] < target已确定 mid 无用)。

• 返回值纠结：有人循环结束后不知该返回 left、right 还是 mid,于是各种特判。记住结论：左开右闭/右开两种写法下，循环结束left == right,统一返回 left,它就是 lower bound。

可复用模板

本题抽象出的是lower bound 模板(第一个 >= target 的下标)，它是二分家族的母版：

java

class Solution { public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length; // 右开区间 [0, n) while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; // mid 无用,丢弃 } else { right = mid; // mid 可能是答案,保留 } } return left; // 第一个 >= target 的下标 } }

注意模板里没有== target提前返回——lower bound 语义下它不是必要的：即使命中，循环也会收敛到第一个等于的位置。提前 return 只是本题的小优化(数组无重复时正确)，有重复元素的题(如 34)绝不能提前返回，否则拿到的不是第一个位置。

变体提示：

• upper_bound(第一个 > target 的下标)→ 把<改成<=:if (nums[mid] <= target) left = mid + 1;。
• 在有序数组里找“最后一个 <= target”→ 即upper_bound - 1,别自己另写一套边界。
• 左闭右闭风格→right = n - 1; while (left <= right),小于时left = mid + 1,大于时right = mid - 1,结束返回left。两套约定二选一，全篇保持一致，绝不能混用。

相似题及区别

• LeetCode 704 二分查找：本题的“纯查找”版，只要求返回 -1 或下标，不涉及插入位置；本题把它推广成 lower bound,返回值永远是合法下标。

• LeetCode 34 在排序数组中查找元素的第一个和最后一个位置：数组含重复元素，需要分别求 lower bound 和 upper_bound 再相减；正是本题模板“不能提前 return”的原因所在。

• LeetCode 278 第一个错误的版本：判断函数抽象成isBadVersion(mid),求“第一个 true”的位置，就是 lower bound 的布尔版本；收缩逻辑和本题完全同构。

• LeetCode 69 x 的平方根：二分的答案不在数组里，而在1~x 的整数域上(“猜一个数，平方后和 x 比较”)，即“二分答案”；收缩判断从nums[mid] < target变成mid * mid <= x,框架不变。