搜索插入位置LeetCode热题100：二分查找边界条件与Java实现详解

LeetCode热题100里有一道搜索插入位置，题面简单到只有一句话：给定一个排序数组和一个目标值，在数组中找到目标值，如果不存在，则返回它将会被按顺序插入的位置。很多第一次刷到它的人觉得这题不过如此，暴力for循环从头扫一遍就能过。真正让人翻车的，是面试官紧接着补一句：“能不能用O(log n)的二分查找来实现？”我当年第一次写二分版的时候，就栽在边界条件上——返回left还是返回mid，right初始化为nums.length还是nums.length - 1，循环条件是left < right还是left <= right，这几个选择之间稍有差池，结果就会完全跑偏。

这篇就把搜索插入位置这道题彻底拆开讲透。适合正在刷LeetCode热题100的同学，也适合准备面试时想把二分查找讲明白的开发者。我会把题意的四个边界场景、循环不变量的写法、Java的两种标准实现、以及高频踩坑点全部过一遍，最后还会聊聊从这道题延伸出去的二分查找通用套路。如果你之前只是背模板过题，这篇文章能帮你把二分查找的“为什么”补上。

1. 题目本身不算难，但“插入位置”这四个字藏着关键陷阱

1.1 先看清题意：要的是下标，不是“找没找到”

先还原一下题目原貌。给定一个升序排列的整数数组nums和一个目标值target，要求返回target在数组中的索引。如果target不存在，则返回它被按顺序插入后应该占据的索引。题面强制要求算法时间复杂度为O(log n)。

这里有个容易被忽略的细节：题目要的不是“找到返回下标，找不到返回-1”，而是“找不到时也要给出一个合法的插入下标”。这个下标必须满足一个条件——把它作为插入点后，数组依然保持升序。换句话说，你返回的答案本质上是一个位置，而不是一个“存在性”的结论。

所以，这道题和普通的二分查找有一个关键区别：普通二分只关心target是否在数组里，存在就返回位置，不存在就返回-1；而搜索插入位置要求你在“不存在”的情况下，也得给出一个逻辑上正确的落点。这也是“插入位置”这四个字带来的第一层迷惑性。

看一个具体例子，nums = [1, 3, 5, 6]：

• target = 5，存在，返回下标2；
• target = 2，不存在，2应该插在1和3之间，也就是下标1的位置；
• target = 7，不存在，7比6还大，应该追加到数组末尾，返回下标4（正好等于数组长度）；
• target = 0，不存在，0比1还小，应该插到最前面，返回下标0。

从这四类结果里能提炼出一个统一规律：要返回的其实是“第一个大于等于target的下标”。这句话是整道题的题眼。为什么它能把“找到”和“没找到”统一起来？因为如果target存在，第一个大于等于target的位置恰好就是target本身所在的位置；如果target不存在，那第一个大于等于target的位置正好是它应该被插入的位置。想明白这一点，后面写二分循环体时，逻辑就不会犹豫。

1.2 四类边界场景的自然语言推演

为了方便记忆，可以把上一小节的四类情况整理成一个表格：

如果用暴力法实现，逻辑就是：从头到尾遍历数组，遇到第一个大于等于target的元素就直接返回它的下标；如果遍历完都没遇到，就返回数组长度。这个方案是对的，复杂度O(n)，但题目明确要求O(log n)，所以必须上二分。

还有一个值得注意的点：答案的上界是数组长度，而不是数组长度减一。很多人在这一步就埋下了隐患——他们下意识认为“下标最大只能是length - 1”，于是把二分右边界初始化成nums.length - 1。这个习惯在普通二分里没问题，但在“插入位置”这道题里，会把“插到末尾”这个合法答案直接排除在搜索区间之外。怎么解决，后面讲右边界初始化时我会详细说。

2. 二分查找在这里的真正作用：逼近不变量

2.1 循环不变量：left左边永远小于target

二分查找的模板很多，但如果你只背模板不看内部逻辑，遇到边界条件稍微变一变就会写错。搜索插入位置这道题，正确的切入方式是先定义清楚循环不变量。

我用左闭右开区间来解释，这也是我认为最适合这道题的写法。定义两个指针left和right，约定：

• 搜索区间是[left, right)；
• left左侧的所有元素都严格小于target；
• right右侧的所有元素都大于等于target。

在这个约定下，循环要做的只有一件事：不断缩小[left, right)这个区间，同时保持上述两条性质不被破坏。等left和right相遇时，区间为空，此时left左侧的元素都小于target，left及其右侧的元素都大于等于target，那么left本身就是“第一个大于等于target的位置”——也就是题目要求的答案。

为什么每次要这样更新指针？看两个分支：

• 当nums[mid] < target时，mid这个位置上的元素小于target，它不可能成为答案，而且mid左侧的元素也一定小于target（因为数组升序）。所以搜索区间可以直接缩到[mid + 1, right)，让left = mid + 1。
• 当nums[mid] >= target时，mid有可能是答案，但它左边可能还有更小的元素也满足“大于等于target”的条件。所以不能直接排除mid，只能把right收缩到mid，让搜索区间变成[left, mid)。

整个过程就像用两把尺子从两侧往中间夹，直到夹缝消失。这就是二分查找在这道题里的真正作用：不是在“寻找某个值”，而是在“逼近一个边界”。

2.2 为什么right的初始值必须是nums.length而不是nums.length - 1

这是搜索插入位置最经典的坑，没有之一。

先看错误写法可能带来的后果。如果right初始化为nums.length - 1，搜索区间就变成了闭区间[left, right]，此时目标值大于所有元素的情况永远无法被正确处理。因为答案nums.length从一开始就被排除在区间外，无论你怎么收缩，left最多只能收敛到nums.length - 1，除非你额外写一行补丁判断。

有人可能会说：“我在最后加一个if (nums[left] < target) return left + 1不就行了？”确实能过测试用例，但这是打补丁，不是理解问题。它会让你在面试中越讲越心虚，因为补丁的本质是承认自己的搜索区间没有覆盖所有可能的答案。

正确的做法是：right = nums.length，把“数组最后一个元素之后”也当作一个合法的候选位置。这样当target大于所有元素时，二分会自然地让left收敛到nums.length，不需要任何额外判断。理解了这个点，你才算真正理解“插入位置”这道题和下界函数的联系。

如果你习惯用左闭右闭区间（right = nums.length - 1），也并不是完全不可行，但要清楚在这种情况下，“第一个大于等于target的位置”是通过left指针在退出循环时的值来表达的，而不是right。两种区间约定最终都能得到正确结果，关键是你得把整个搜索过程遵循的区间语义保持一致。

2.3 返回left而不返回mid的原因

很多人写完二分会顺手写return mid，然后发现结果不对，百思不得其解。原因在于，mid是循环体内部临时计算出来的中间位置，循环每执行一次，mid都会变化。当循环结束时，最后一次计算出的mid，不一定等于收敛后的left。

举例说明。比如上面提到的target = 2，nums = [1,3,5,6]的推演过程里，mid的取值依次是2、1、0，而最终答案是left = 1。最后一次mid是0，如果return mid，答案就错了。除非你在循环中及时捕获“nums[mid] == target”的情况然后立刻返回，否则循环结束后返回mid就是碰运气。

其实在标准左闭右开写法里，循环结束时left和right是相等的，所以return left或return right都行。我更推荐return left，原因是它的语义最清晰：left代表“第一个大于等于target的下标”，这正是题目要的答案。好的二分代码应该是“不变量驱动”的——是什么就返回什么，而不是靠某个中间变量的巧合。

3. Java实现版本对比：标准写法、左闭右闭写法与暴力法的差异

3.1 标准左闭右开写法：最推荐的一版

直接上代码。这是我认为最适合搜索插入位置的Java实现，也是我日常写二分时默认的区间约定：

class Solution { public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length; // 循环不变量： // [left, right) 为搜索区间 // left 左侧的元素都严格小于 target； // right 右侧的元素都大于等于 target。 while (left < right) { int mid = (left + right) >>> 1; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } }

用nums = [1, 3, 5, 6]，target = 2手动推演一遍：

• 初始：left = 0，right = 4，mid = 2，nums[2] = 5 >= 2，所以right = 2；
• 此时：left = 0，right = 2，mid = 1，nums[1] = 3 >= 2，所以right = 1；
• 此时：left = 0，right = 1，mid = 0，nums[0] = 1 < 2，所以left = 1；
• 此时：left = 1，right = 1，循环结束，返回left = 1。

结果正确。再看target = 7的情况：

• left = 0，right = 4，mid = 2，nums[2] = 5 < 7，left = 3；
• left = 3，right = 4，mid = 3，nums[3] = 6 < 7，left = 4；
• left = 4，right = 4，循环结束，返回4。

正好是数组长度，完美覆盖“插到末尾”的场景，不需要任何额外补丁。

3.2 另一种可行写法：左闭右闭区间

如果你习惯了教科书里常见的“左闭右闭”写法，也可以用下面这版：

class Solution { public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = (left + right) >>> 1; if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; } }

这版的思路是：当nums[mid] >= target时，mid不可能是最终答案吗？不一定，mid可能是答案，只是我们要找的是“第一个”大于等于target的位置，所以在nums[mid] >= target时，不能直接把right收缩到mid然后保留mid，而是要把right收缩到mid - 1，相当于把mid先排除掉，最终left会收敛到我们要的位置。

推演target = 2，nums = [1, 3, 5, 6]：

• left = 0，right = 3，mid = 1，nums[1] = 3 >= 2，right = 0；
• left = 0，right = 0，mid = 0，nums[0] = 1 < 2，left = 1；
• left = 1，right = 0，退出循环，返回左 = 1。

再看target = 7：

• left = 0，right = 3，mid = 1，nums[1] = 3 < 7，left = 2；
• left = 2，right = 3，mid = 2，nums[2] = 5 < 7，left = 3；
• left = 3，right = 3，mid = 3，nums[3] = 6 < 7，left = 4；
• left = 4，right = 3，退出循环，返回left = 4。

也正确。这版写法的关键在于，最终答案是通过left指针暴露出来的——退出循环时，left恰好是第一个大于等于target的位置。因为它不需要维护右开边界，所以right = nums.length - 1不会导致“末尾插入”场景漏解。

不过个人建议：二选一即可，不要两种来回切换。我自己更推荐左闭右开写法，因为它把“数组末尾之后”也天然包含在搜索空间里，逻辑上更统一，也方便以后迁移到其他二分变体。

3.3 复杂度对比：O(n)和O(log n)的差距有多大

暴力遍历的时间复杂度是O(n)，二分查找是O(log n)。简单算一笔账：

当数组长度达到百万级别时，暴力法可能要扫描上百万个元素，二分最多只需要20次比较。排序数组加查找目标值加O(log n)要求，这三个条件放在一起，基本就是二分查找的身份证。面试官出这道题，考察的就是你能不能识别出“有序数组 + 查找 + 对数复杂度”这个经典组合。

4. 高频踩坑清单：while条件、中间值溢出、死循环风险

4.1 mid计算用(left + right) >>> 1而不是(left + right) / 2

先看一个容易被忽略的问题：如果left和right都很大，比如left = 1_500_000_000，right = 1_500_000_000，两者相加是3_000_000_000，超出了int的最大值2_147_483_647。在Java里，这个加法会溢出成负数，此时再除以2，得到的mid就是错的，甚至可能是负数，会导致数组越界。

实际刷题时，题目给出的数组长度很少会触发这个边界，所以很多人在LeetCode上跑得好好的，一到面试官追问就露馅了。正确的写法有两种：

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

或者：

int mid = left + (right - left) / 2;

这两种写法都能避免加法溢出。第一种用的是无符号右移，把left + right先转成无符号语义再除以2；第二种是先算差值再除以2，从数学上就不会溢出。两种都行，我个人习惯用第一种，写起来更简洁——但要记得用户自己理解这个写法是怎么回事，而不是抄一个看起来高级的符号。

4.2 while (left < right)和while (left <= right)的选择

这是二分查找最常见的“问答题”。结论是：循环条件的写法必须和你的区间约定配套。

• 如果是左闭右开写法（right = nums.length），用while (left < right)，退出循环时left == right；
• 如果是左闭右闭写法（right = nums.length - 1），用while (left <= right)，退出循环时left = right + 1。

问题往往出在混搭。比如你一开始写了right = nums.length，却用while (left <= right)，当left和right相等时还会再进一次循环。若此时nums[mid] >= target，right会被赋值为mid，也就是等于left，left和right都不变，下一次循环还是一样的状态，死循环就出现了。这种错误在本地调试时非常隐蔽，因为不是每次用例都会触发，只有恰好收敛到left == right且nums[mid] >= target时才会卡住。

所以写二分前，先在心里确认：你的搜索区间是开还是闭？这会直接决定循环条件、指针更新方式和初始值三者之间的搭配。

4.3 数组为空和只有一个元素：两个极端用例的验证

LeetCode原题通常保证数组长度至少为1，但面试官很喜欢把你逼到极端。先看空数组的情况：如果nums.length == 0，左闭右开写法里left = 0，right = 0，while条件不成立，直接返回0。含义也很自然：空数组里插入任何元素，位置都只能是0。写都不用额外判断。

再看只有一个元素的情况。nums = [2]，target = 1：

• 左闭右开：mid = 0，nums[0] = 2 >= 1，right = 0，循环结束，返回0。正确。
• 左闭右开：target = 3时，mid = 0，nums[0] = 2 < 3，left = 1，循环结束，返回1。正确。

单个元素时，两种写法都能正确覆盖“小于”和“大于”两种情况。如果target恰好等于2，返回0也对，因为第一个大于等于2的位置就是下标0。这几个极端用例，建议你在写完后都手动推演一遍，能有效避免“大部分用例过了但特殊场景挂了”的尴尬。

5. 从这道题看二分查找的通用套路，以及面试时的加分回答

5.1 搜索插入位置的本质是lower_bound：一套通用四步法

这道题在计算机科学里有一个更正式的名字：lower_bound，即返回第一个大于等于target的位置。如果你掌握了这个视角，很多二分变体都可以统一到一个套路下。

我自己的经验是，写任何二分都按四步走：

1. 确定搜索区间的开闭性。选左闭右开还是左闭右闭，决定了后续所有写法。
2. 写清楚循环不变量。用一句话说明left左侧是什么、right右侧是什么。
3. 根据不变量决定指针更新。nums[mid] < target时怎么动，nums[mid] >= target时怎么动，必须和不变量严格对应。
4. 确定循环结束后的返回值。想清楚此时left表示什么含义，然后直接返回。

用这套方法可以推出一大堆二分变体：

• “查找第一个等于target的位置”：就是lower_bound的结果再验证一下nums[left] == target；
• “查找最后一个等于target的位置”：可以转换成查找“第一个大于target的位置”再减一；
• “查找第一个大于target的位置”：把nums[mid] < target和nums[mid] >= target的分支改成nums[mid] <= target和nums[mid] > target即可。

LeetCode上有好几道题都是这个套路的不同包装：在排序数组中查找元素的第一个和最后一个位置、第一个错误的版本、寻找峰值、旋转排序数组中的最小值……本质上都在考察你对“边界条件”和“不变量”的把握。

5.2 面试官追问时的加分回答

面试时如果只扔出一段能跑的代码，基本等于没答。面试官真正想听的是你对二分查找“边界为什么这么写”的解释。我建议在写完代码后主动补一句：

“我维护的循环不变量是：left左侧的所有元素都小于target，right右侧的所有元素都大于等于target。循环退出时，left就是第一个大于等于target的位置，所以直接返回left。”

这句话一出来，面试官基本就能判断你是真的理解还是在背模板。如果再被追问“为什么right初始化为nums.length”，你就回答“因为答案可能落在数组末尾之后，所以要把这个位置纳入搜索区间”。

还有一个冷门加分项：如果面试官问“Java里有没有现成的方法”，你可以提到Arrays.binarySearch。当它找不到目标时，返回的是-(insertionPoint) - 1，取反再减1就能得到插入位置。但大多数面试场景下，面试官希望你手写二分，而不是调用库函数。这个提到一下可以，但别把它当主答案。

5.3 从算法题迁移到工程场景：二分的价值不止于刷题

搜索插入位置不只是一道面试题，它背后的lower_bound思想在工程里极其常见。举几个例子：

• 在有序的时间戳列表里定位某条日志所在的位置；
• 在配置表中找到不大于某个数值的最大档位（比如根据积分查找对应等级）；
• 在版本列表中快速定位某个版本号之后的下一个版本；
• 数据库索引的B+树查找也大量依赖类似的“下界”思想。

理解了“查找第一个不小于目标值的位置”这个抽象概念，你会发现在很多有序数据场景里，你都能自然想到用二分而不是线性扫描。这道题虽然简单，但它是通往这些真实应用的一扇小门。

最后分享一个我自己的习惯：每道二分题，我都会先把循环不变量用注释写在代码上方，再开始写循环体。写完也不会直接提交，而是把题目里的四类典型输入——存在、不存在但夹在中间、大于所有元素、小于所有元素——在脑海里或者草稿纸上完整推演一遍。这套动作看起来多花一两分钟，但真的帮我避开了无数边界错误。搜索插入位置不难，但它是我见过最适合用来检验你对二分查找理解深度的一道题。如果你能把这道题对答如流，再去做在排序数组中查找元素的第一个和最后一个位置、寻找旋转排序数组中的最小值这些题，会觉得顺理成章、一通百通。