二分查找边界问题：一套模板搞定查找首尾与插入位置

刷算法题的人，基本都会撞上二分查找，而二分查找里最容易被“看似简单、一写就错”绊倒的，就是排序数组中的边界问题。很多题库里都有这样两道相邻的题：一道要求找出目标值在排序数组中第一次和最后一次出现的位置，另一道要求返回目标值应该被插入到数组的哪个下标。这两道题表面上一前一后、互不相干，但只要把二分的本质想透了，它们根本就是同一道题，而且能共用一个极其稳妥的模板。

我一直觉得，二分查找的关键不是“背模板”，而是理解每一轮循环里区间到底在维护什么。这篇文章就从排序数组里的“第一个位置、最后一个位置、搜索插入位置”这三个问题入手，把边界二分的思路、手推过程、坑点和统一模板一起讲透。适合刚开始学二分、或者已经会写简单二分但一遇到重复元素就发懵的读者，看完之后你至少能稳稳写出不出死循环的二分代码，也能在面试里把自己的选择讲明白。

1. 两个经典题，本质是同一个问题：边界定位

1.1 为什么“第一个位置 + 最后一个位置”永远成对出现

先还原一下题目场景。有一个升序排列的整数数组，比如[1, 2, 3, 3, 3, 5, 7]，里面可能存在重复元素。现在给你一个目标值target，要求返回它第一次出现的下标和最后一次出现的下标，如果数组里根本没有这个值，就返回[-1, -1]。

很多人的第一反应是：这还不简单，先线性扫描一遍，从头找到第一个等于 target 的下标，再从尾找到最后一个等于 target 的下标。这样确实能做对，但时间复杂度是 O(n)。在数组长度特别大、或者目标值出现频率特别高的情况下，这个解法大概率过不了题目对时间复杂度的限制。而二分查找可以把时间降到 O(logn)，这也是这类题真正的考察点。

这里有一个非常关键的性质：因为数组是升序的，所有等于 target 的元素在数组中必然形成一段连续的区间，不可能东一个西一个。所以“找第一个位置”和“找最后一个位置”，本质上就是在找这段连续区间的左端点和右端点。一旦想通这一点，你就会发现这道题不是“找两次元素”，而是“找两个边界”，两个边界问题用两次二分来解，完美契合。

1.2 搜索插入位置的隐藏身份

再看第二道题。同样是升序排序数组，给一个 target，要求返回它应该插入的位置，插入之后数组依然保持升序。比如[1, 3, 5, 6]，如果 target 是 5，答案是 2；如果 target 是 2，答案是 1；如果 target 是 7，答案是 4；如果 target 是 0，答案是 0。

这道题看起来和“查找第一个/最后一个位置”没有直接关系，但它真正的名字叫 lower_bound：在有序数组中，找到第一个大于等于 target 的元素下标。这个下标同时满足两种语义：如果 target 存在，这个下标就是它自己的位置；如果 target 不存在，这个下标就是它应该插入的位置，插入后它左边的元素都小于它，右边的元素都大于等于它。

所以你看，34 和 35 这两道题，一个在求左右边界，一个在求 lower_bound，看起来是三类问题，实际上都在做同一件事：在一个有序序列里，通过不断缩小搜索区间，定位一个满足特定边界条件的下标。这就是为什么我把它们放在一起讲，学一个模板，三道题全通。

1.3 适合谁来读这篇

这篇文章的定位，是给那些有一定编程基础、但二分查找总是写得磕磕绊绊的人看的。如果你只是会背一个最简单的二分模板，一旦数组里有重复元素就不知道等于 target 时该往哪边收缩，那你读完至少能建立起一套自己的不稳定区间思维。如果你是为了面试准备，那这篇文章给你的不只是代码，还有面试官大概率会追问的“为什么这样收缩”“为什么不会死循环”“mid 为什么这样取”这些细节。

2. 二分老写错的根因：不变量没守住

2.1 二分不是“猜数游戏”，是区间收缩

很多教程喜欢把二分讲成猜数字游戏：每次猜中间，大了往左，小了往右。这个比喻方便理解，但很危险，因为它给人一个错觉，觉得二分就是“找到一个符合条件的数就停下”。一旦遇到重复元素、要寻找边界，或者目标值不存在，这种“猜中即停”的思维就会出问题。

真正严谨的理解应该是：二分每一轮维护的是一个区间，这个区间必须始终“包含所有可能成为最终答案的下标”。每比较一次 nums[mid] 和 target，我们都能排除掉区间的一半，因为根据有序性，被排除的那一半里不可能再有答案。只要这个“不变量”——区间始终覆盖所有潜在答案——不被破坏，二分就一定是正确的。

我见过太多人写二分出错，不是因为比较符号写反，而是因为不变量在循环过程中被悄悄破坏了。最常见的破坏方式有两种：一是更新 left 或 right 时，把已经完全确定不可能成为答案的 mid 又塞回区间里；二是把区间定义从闭区间改成开区间时，left 和 right 的初值、更新规则没有同步调整。

2.2 死循环是怎么发生的

死循环是二分新手遇到的最大的坑。你写了一个看起来没问题的二分，结果程序卡住不动，或者在某些输入下疯狂循环。原因很简单：循环里 left 和 right 没有向彼此收敛，某个边界一直原地踏步。

举一个很经典的错误场景。假如你用while (left < right)这个循环条件，且采用mid = (left + right) / 2（向下取整），然后在某种情况下写了left = mid。当 left = 4, right = 5 时，mid = 4，如果走到left = mid，下一轮还是 left = 4, right = 5，mid 还是 4，于是无限循环。这种情况下，mid 向下取整导致 left 永远都追不上 right。

要解决这个问题，有两种思路。第一种是改用向上取整：mid = left + (right - left + 1) / 2，这样当 left = 4, right = 5 时 mid = 5，可以让 left 和 right 真正相遇。第二种更保险的思路是，干脆设计一个永远不需要left = mid的模板。后面要讲的半开区间模板[left, right)就是这种设计，它只使用left = mid + 1和right = mid，每轮区间长度严格减小，从数学上杜绝了死循环的可能性。

2.3 溢出处理

二分还有一个看起来很基础、但很多人忽略的细节：mid = (left + right) / 2在 left 和 right 都很大的时候可能溢出。比如 left 和 right 都接近 Integer.MAX_VALUE，二者相加就超过 int 的范围了。

更稳的写法是int mid = left + (right - left) / 2;。因为 right 和 left 都是合法数组下标，差值不会溢出，加上 left 之后依然在 int 范围内。用位运算写成left + ((right - left) >> 1)也行，但位运算优先级容易记错，我建议就老老实实写除法，可读性更好，也不容易出幺蛾子。

3. 查找第一个等于 target 的位置：等于也不放过

3.1 从“找任意一个”升级到“找最左边”

如果你之前会写经典二分，那么你很可能已经习惯这种写法：当nums[mid] == target时，直接 return mid。这个写法在数组里没有重复元素时非常好用，一旦有重复元素，它只能保证你返回“某一个”等于 target 的下标，不能保证是第一个。

要让算法返回第一个等于 target 的位置，核心改动只有一个：当nums[mid] == target时，不能停，要收右边界，继续向左搜索。换句话说，判断逻辑应该写成“如果 nums[mid] >= target，说明答案可能在 mid 位置或者更左边，所以把 right 收到 mid；如果 nums[mid] < target，说明答案一定在 mid 右边，所以把 left 收到 mid + 1”。

这里我们用半开区间写法，初始left = 0，right = nums.length，循环条件是while (left < right)。它的含义是：当前搜索区间是[left, right)，right 不包含在区间内。退出循环时一定有 left == right，这个值就是第一个大于等于 target 的下标。

3.2 半开区间模板与手推过程

以nums = [1, 2, 3, 3, 3, 5, 7]，target = 3为例，手推一遍：

返回 2，正好是第一个 3 的下标。注意第 3 轮里 mid = 2 时 nums[mid] 等于 target，但我们没有停下，反而把 right 收到了 2，之后 left 也变成了 2，区间变成空，循环终止。这个“等于也收缩”的操作，就是整个左边界查找的灵魂。

对应的代码也很简洁：

int lowerBound(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; }

3.3 结束后如何处理

lowerBound 返回的是“第一个大于等于 target 的下标”，这个下标本身还不能直接作为答案，因为 target 可能根本不存在。所以查找第一个位置时，代码要补一个判断：

int first = lowerBound(nums, target); if (first == nums.length || nums[first] != target) { return -1; } return first;

这个判断同时处理了两种情况：数组里没有 target（nums[first] != target），以及 target 比所有元素都大（first == nums.length）。比如数组是[1, 3, 5, 7]，target = 6，lowerBound 返回 3，nums[3] = 7 != 6，返回 -1，正确。

4. 查找最后一个等于 target 的位置：对偶问题

4.1 思路翻转

找最后一个等于 target 的位置，最直接的对称思路是：找到第一个大于 target 的位置，然后往前挪一位。这个“第一个大于 target 的位置”在标准库里通常叫 upper_bound。

实现上，它和 lowerBound 只有一处不同：比较条件从nums[mid] < target改成nums[mid] <= target。当nums[mid] <= target时，说明答案可能在 mid 右边或者就是 mid 本身，所以把 left 收到 mid + 1，继续向右搜索；当nums[mid] > target时，把 right 收到 mid。退出时返回的 left，就是第一个大于 target 的下标。

用同一个数组nums = [1, 2, 3, 3, 3, 5, 7]，target = 3手推一遍：

返回 5，它指向的是数组中第一个大于 3 的元素 5。最后一个等于 target 的下标就是upperBound - 1，也就是 4，对应数组中最后一个 3，正确。

代码同样很短：

int upperBound(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) { left = mid + 1; } else { right = mid; } } return left; }

4.2 三个细节

这里有几个细节值得单独说。

第一，upperBound 的返回值可能是 0，此时upperBound - 1是 -1，直接拿去访问数组就会越界。所以拿到右边界后，要判断rightIndex >= 0 && rightIndex < nums.length && nums[rightIndex] == target。因为 upperBound 本来表示的是“第一个大于 target 的位置”，当它等于 0 说明所有元素都大于 target，那么“上一个位置”自然不存在。

第二，不要试图在同一个二分循环里同时记录“第一个”和“最后一个”。我见过有人试图用两个变量分别保存 candidate，然后在一个 while 循环里塞进所有逻辑，结果等号方向一多，自己先绕晕了。既然左右边界二分一次都是 O(logn)，两次二分合起来还是 O(logn)，完全没必要为了省一次循环增加理解成本。

第三，lowerBound 和 upperBound 是一对完美的对偶函数。前者把大于等于 target 的都往左赶，后者把小于等于 target 的都往右赶。你在心里记住“lower 找左、upper 找右”这个口诀，写代码时方向就不会搞反。

4.3 整体封装

把左右边界放在一起，查找范围的完整代码就是：

public int[] searchRange(int[] nums, int target) { int first = lowerBound(nums, target); if (first == nums.length || nums[first] != target) { return new int[]{-1, -1}; } int last = upperBound(nums, target) - 1; return new int[]{first, last}; }

空数组的情况也被自动处理了：nums.length为 0 时，lowerBound 返回 0，first == nums.length成立，直接返回[-1, -1]。

5. 搜索插入位置：一句话翻译成 lower_bound

5.1 极端情况推演

搜索插入位置这道题，如果你拿[1, 3, 5, 6]这个数组去反推，会发现所有情况都能归结为三种：target 比所有元素大，答案就是数组长度；target 比所有元素小，答案是 0；target 介于两个元素之间，答案就是第一个大于等于它的位置。比如：

• target = 5，数组里有，答案 2。
• target = 2，数组里没有，应该插在 1 和 3 之间，答案 1。
• target = 7，比所有元素大，答案 4。
• target = 0，比所有元素小，答案 0。

这四种情况，其实都可以由一个函数统一返回：lowerBound(nums, target)。它天然返回第一个大于等于 target 的下标，target 存在时就是它自己的位置，target 不存在时就是应该插入的位置。

5.2 lowerBound 直接当答案

所以搜索插入位置的题解，几乎就是直接把前面那个 lowerBound 拿过来用：

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

你会发现一个很有趣的事实：这段代码和第三章的 lowerBound 一模一样，连返回值都不用加工。这就是为什么我说这两道题本质是同一道题——你在做“查找第一个等于 target 的位置”时，先调了 lowerBound，再判断存不存在；你在做“搜索插入位置”时，把 lowerBound 的返回值直接当答案。区别只在于怎么解释这个返回值。

5.3 和内置二分的关联

如果你用过 Java 的Arrays.binarySearch，可能会疑惑：它为什么在找不到目标时返回一个负数，而且负数的值还很奇怪？比如Arrays.binarySearch(new int[]{1, 3, 5, 6}, 2)返回 -2。

Java 的规则是这样的：如果找到了，返回目标下标；如果没找到，返回-(insertionPoint) - 1。这里的 insertionPoint 就是第一个大于目标值的位置，也就是 lowerBound 的返回值。对 target = 2 来说，lowerBound = 1，所以返回-1 - 1 = -2。之所以要减 1，是因为 0 已经被“找到了且下标为 0”占用了，必须用负数区分“没找到”和“找到了下标 0”。

理解了 lowerBound 之后，你再看这个返回值就不会觉得它神秘了，它本质上就是把“应插入位置”编码成了一个负数。很多语言的标准库都用类似的约定，这个底层逻辑是相通的。

6. 一个模板打天下：lowerBound + upperBound 的收尾封装

6.1 最终代码

把前面几章的思路整合起来，我推荐你直接记住下面这组代码。它只有一个模板套路，可以解决查找第一个位置、最后一个位置、搜索插入位置三个问题。

public class BinarySearchBound { // 第一个 >= target 的下标（lower_bound） public int lowerBound(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } // 第一个 > target 的下标（upper_bound） public int upperBound(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) { left = mid + 1; } else { right = mid; } } return left; } // 查找目标值的第一个和最后一个位置 public int[] searchRange(int[] nums, int target) { int first = lowerBound(nums, target); if (first == nums.length || nums[first] != target) { return new int[]{-1, -1}; } int last = upperBound(nums, target) - 1; return new int[]{first, last}; } // 搜索插入位置 public int searchInsert(int[] nums, int target) { return lowerBound(nums, target); } }

6.2 为什么半开区间最不易错

我用了一整篇文章来铺垫，就是想让你理解最后这个[left, right)半开区间模板的设计逻辑。它的三个特点分别是：

第一，right初始化为nums.length，而不是nums.length - 1。这样 left 和 right 一开始就把整个数组都包在搜索区间里，不会漏掉最后一个元素。有些闭区间模板写成right = nums.length - 1，then最后一轮 left 可能越过 right，返回时还要考虑边界，容易出错。

第二，退出循环时一定有left == right，而且这个值可以直接作为答案。不用纠结最后返回 left 还是 right，它们相等，你怎么写都对。这比闭区间模板在退出后还需要判断 left 是否越界要省心得多。

第三，更新规则只有两种：left = mid + 1或者right = mid。每次更新，区间长度都严格变小，mid 本身绝不会被留在新区间里（除非它正好是新的 right，但 right 是不包含在区间内的）。所以从这个模板的结构上，死循环就被直接排除了。

我自己以前也用过闭区间写法，代码更短，但每次遇到要返回 left 还是 right 的边界问题时，总要多想几秒。后来换成半开区间模板，稳定用了很久，几乎没有再写错过。

6.3 复杂度与后续扩展

这三道题的时空复杂度完全一致：时间 O(logn)，空间 O(1)。因为每轮搜索区间缩小一半，logn 轮就能结束；全程只用了常数个额外变量。

学会了这个模板之后，你可以把它迁移到很多场景。比如二维矩阵中搜索目标值，本质上是把二维坐标映射成一维坐标，再用一次二分；再比如求一个数的平方根的整数部分，可以把这个数看成隐式的有序数组，然后二分答案；还有旋转排序数组里找最小值、找目标值，虽然判断条件需要额外处理，但区间收缩的基本骨架是一样的。算法题里最值得投资的，往往就是这种能一鱼多吃的核心模板。

7. 我的实测建议：测试用例、调试手段与理解重心

7.1 必测的边界用例

算法代码写完，不是看一眼觉得对就完事了。我每次写完二分，都会跑一遍下面这组边界用例，这几类情况几乎覆盖了所有二分查找容易出错的地方：

我特别提醒全相同这个用例。如果你写的二分在“等于 target 时直接返回”，在这个用例下会返回一个中间位置，但你要的是第一个和最后一个，结果就会错。用上面这个测试表，能在 5 分钟之内帮你把代码的边界问题全暴露出来。

7.2 调试二分的一个实用技巧

如果真的出现死循环或者结果不对，我建议别盯着代码空想，直接在循环里打印每一轮的 left、right、mid、nums[mid] 和比较方向。比如在 while 循环里加一行日志：

System.out.println("left=" + left + ", right=" + right + ", mid=" + mid + ", nums[mid]=" + nums[mid] + ", target=" + target);

打印出来后，死循环的原因基本一眼就能看出来：要么 left 卡在某个值不动，要么 right 卡在某个值不动，要么 mid 一直等于 left。看到卡住的地方，就去检查对应的更新分支是不是把 left 或 right 推回了原位。这把问题定位到具体某一轮循环之后，修复就是改一行代码的事。

7.3 理解比背模板重要

最后说点带个人体会的话。二分查找这个知识点，很多人觉得简单，但一面试就露馅。原因就在于背模板的人只能写出“标准答案”，一旦面试官换了个角度问“为什么等于 target 时你要收缩右边界”，或者“如果数组长度是 2 的幂会怎样”，就答不上来了。

我强烈建议你在理解了这套半开区间逻辑之后，自己从零推导一遍，不要直接抄代码。推导时反复问自己几个问题：我的区间里包含的是哪些下标？区间收缩后，被排除的那部分里为什么不可能存在答案？循环退出时 left 指向的到底是什么语义？只要能把这三个问题想通，你以后再遇到任何二分的变种题，都有底气现场推演，而不是祈祷题目和背过的模板吻合。

每次面试或者写题遇到二分，我都会默念一遍这六个字：左边取不到，右边取不到。left 更新时加一，right 更新时不加一，这样区间永远在收缩，边界语义也永远清晰。这套模板和思路我用了很久，确实是三条题一条路，踩过的坑都变成了肌肉记忆。