写对二分查找有多难？Java集合框架的作者也曾栽在一行mid计算上

写在前面

二分查找大概是最短小精悍的算法之一——核心逻辑十几行代码，思路小学生都能听懂：每次看中间的数，比目标大就往左找，比目标小就往右找。但就是这么简单的算法，历史上真出过一次经典翻车：java.util.Arrays和java.util.Collections里的二分查找实现，在将近十年的时间里都藏着一个溢出bug，直到2006年才被时任Google工程师、《Effective Java》作者Joshua Bloch写博客揭出来。这篇就顺着这个真实案例，把二分查找容易写错的几个边界点讲透。

一、是什么：靠"砍半"逼近目标

二分查找解决的是在有序数组里判断某个目标值在不在、在哪的问题。核心动作只有一步：拿数组中间位置的值和目标比较——相等就找到了；比目标小，说明目标只可能在右半区间，把搜索范围收缩到右边；比目标大，同理收缩到左边。每比较一次，搜索区间就砍掉一半，一个长度为n的数组最多比较log2(n)次就能确定结果，这也是它时间复杂度O(logn)的来源。

flowchart LR
    A[区间left到right] --> B[取中间mid]
    B --> C{arr的mid<br/>等于target吗}
    C -- 相等 --> D[命中返回]
    C -- mid处的值偏小 --> E[往右收缩<br/>left变成mid加1]
    C -- mid处的值偏大 --> F[往左收缩<br/>right变成mid减1]
    E --> G{区间还有效吗}
    F --> G
    G -- 有效 --> A
    G -- 无效 --> H[没找到返回-1]

二、为什么：思路简单，边界条件却处处是坑

先说那个真实的历史bug。教科书和早期JDK实现里，取中间下标的写法几乎都是mid = (left + right) / 2——left和right都是int类型，一旦数组长度足够大（left + right超过Integer.MAX_VALUE，也就是约21亿），这个加法本身就会先溢出成一个负数，再除以2还是负的，直接导致数组越界。Joshua Bloch在2006年那篇文章里指出，JDK自己的java.util.Arrays.binarySearch和Collections.binarySearch里就是这个写法，这个bug潜伏了大约九年才被发现——原因很直白：大多数人测试二分查找只会用几十上百个元素的小数组，根本触发不到21亿这个量级。

修复方式是把mid = (left + right) / 2换成mid = left + (right - left) / 2：right - left是数组的长度差，不会超过数组本身的长度，不可能溢出，加上left之后自然就是正确的中间下标，数学上完全等价，只是换了个不会溢出的算法。这个案例说明的道理是：二分查找出错往往不是思路错了，而是这些看起来无关紧要的边界写法错了，而且这类错误在小规模测试下完全不会暴露。

除了溢出，二分查找还有两类经典的边界坑，都跟"循环什么时候停、区间怎么收缩"有关：

• 循环条件该用left <= right还是left < right：如果写成left < right，当搜索区间只剩最后一个元素（left == right）时，循环会直接判定条件不成立提前退出，这个元素永远不会被比较到，等于凭空漏掉一个候选值。
• 收缩区间时该写mid+1/mid-1还是直接写mid：如果确认arr[mid]不是目标后，把边界更新成left = mid或right = mid而不是mid+1/mid-1，会导致已经确认排除的mid这个位置又被重新纳入下一轮搜索范围，区间可能永远缩小不到空，变成死循环。

三、怎么用：代码实现 + 常见坑

标准二分查找：迭代版本

<span>public</span> <span>static</span> <span>int</span> <span>binarySearch</span><span>(<span>int</span>[] arr, <span>int</span> target)</span> {
    <span>int</span> <span>left</span> <span>=</span> <span>0</span>, right = arr.length - <span>1</span>;
    <span>while</span> (left <= right) {                        <span>// 用 <= 而不是 <</span>
        <span>int</span> <span>mid</span> <span>=</span> left + (right - left) / <span>2</span>;       <span>// 防溢出写法</span>
        <span>if</span> (arr[mid] == target) {
            <span>return</span> mid;
        } <span>else</span> <span>if</span> (arr[mid] < target) {
            left = mid + <span>1</span>;                         <span>// 收缩到mid+1，不是mid</span>
        } <span>else</span> {
            right = mid - <span>1</span>;                        <span>// 收缩到mid-1，不是mid</span>
        }
    }
    <span>return</span> -<span>1</span>;
}

这段代码把上一节提到的三个坑都避开了：防溢出的mid计算、left <= right的循环条件、mid+1/mid-1的收缩写法，三者缺一个都可能出问题。

边界查找：找重复元素里"最左边"的那个

面试里更常考的其实是变体——数组里有重复元素，要求返回第一个等于target的下标，而不是随便一个匹配位置：

<span>public</span> <span>static</span> <span>int</span> <span>leftBound</span><span>(<span>int</span>[] arr, <span>int</span> target)</span> {
    <span>int</span> <span>left</span> <span>=</span> <span>0</span>, right = arr.length - <span>1</span>;
    <span>int</span> <span>result</span> <span>=</span> -<span>1</span>;
    <span>while</span> (left <= right) {
        <span>int</span> <span>mid</span> <span>=</span> left + (right - left) / <span>2</span>;
        <span>if</span> (arr[mid] == target) {
            result = mid;
            right = mid - <span>1</span>;   <span>// 找到了也不能直接返回，继续往左找更靠前的target</span>
        } <span>else</span> <span>if</span> (arr[mid] < target) {
            left = mid + <span>1</span>;
        } <span>else</span> {
            right = mid - <span>1</span>;
        }
    }
    <span>return</span> result;
}

最容易漏的坑就是找到target后立刻return mid——这样返回的只是随便一个匹配到的位置，不保证是最左边那个。正确做法是先把这个位置记下来，然后当成"没找到、继续往左找"处理（right = mid - 1），直到区间收缩为空，最后记录的那个才是最左边的答案。

递归版本：思路一样，但要留意额外开销

<span>public</span> <span>static</span> <span>int</span> <span>binarySearchRecursive</span><span>(<span>int</span>[] arr, <span>int</span> target, <span>int</span> left, <span>int</span> right)</span> {
    <span>if</span> (left > right) <span>return</span> -<span>1</span>;   <span>// 递归出口对应迭代版的循环条件取反</span>
    <span>int</span> <span>mid</span> <span>=</span> left + (right - left) / <span>2</span>;
    <span>if</span> (arr[mid] == target) <span>return</span> mid;
    <span>return</span> arr[mid] < target
        ? binarySearchRecursive(arr, target, mid + <span>1</span>, right)
        : binarySearchRecursive(arr, target, left, mid - <span>1</span>);
}

递归版本逻辑上和迭代版完全对应（递归出口left > right就是迭代循环条件left <= right的取反），但每次递归调用都有额外的方法调用栈开销，即使递归深度只有O(logn)、不会有栈溢出的风险，工程上处理海量数据的高频查找场景，通常还是优先选迭代版本。

四、面试追问

Q1：为什么mid要写成left + (right - left) / 2，而不是更直观的(left + right) / 2？

因为left和right都是int类型，当数组长度足够大、两者之和超过Integer.MAX_VALUE时，left + right这一步加法本身就会先溢出成负数，算出来的mid是错的，还可能导致数组越界。left + (right - left) / 2在数学上完全等价，但right - left不会超过数组长度，不会发生溢出，是更安全的写法。这个问题在JDK的Arrays.binarySearch里真实存在过近十年才被修复。

Q2：为什么循环条件要写left <= right而不是left < right？

因为搜索区间是闭区间[left, right]，当区间收缩到只剩一个元素时left == right，这个元素依然是合法的候选值，必须进入循环体被比较一次。如果条件写成left < right，这种情况会被提前判定为循环结束，直接跳过对这个元素的比较，导致明明存在的目标值被漏掉。

Q3：查找左边界的场景里，为什么命中target之后不能直接返回？

因为要找的是重复元素里最靠左的那个，而不是随便一个匹配位置。命中之后如果直接返回，返回的下标可能是重复元素中间的某一个，不保证前面还有没有更早的匹配。正确做法是把当前命中的位置先记录下来，然后按"没找到"处理继续收缩右边界（right = mid - 1）向左搜索，直到区间为空，最后一次记录的位置才是真正最左边的答案。

Q4：二分查找的递归实现和迭代实现，工程上更推荐用哪个？

两者时间复杂度都是O(logn)，逻辑完全对应，但递归版本每层递归都有额外的方法调用栈开销，迭代版本只需要几个局部变量，空间复杂度是O(1)。虽然二分查找的递归深度只有O(logn)，不会有栈溢出风险，但涉及高频调用的场景，迭代版本的常数开销更小，工程上通常优先选迭代实现。

下一篇预告

Day06 KMP字符串匹配：next数组到底在记录什么。