Jon Bentley 在他的经典著作《Programming Pearls》中记录了一个令人震惊的实验结果：在贝尔实验室和 IBM 的课程中，他给专业程序员几个小时的时间实现二分查找，结果超过 90% 的人写出了有 bug 的代码。更令人惊讶的是，二分查找算法首次发表于 1946 年，但第一个正确的实现直到 1962 年才出现——整整 16 年间，这个看似简单的算法一直以"错误"的形式流传。

为什么一个只有十几行代码的算法如此难以正确实现？又为什么它在算法面试中占据如此重要的地位？这篇文章将深入剖析二分查找的本质，从标准模板到各种变体，再到 LeetCode 上的经典题目，帮助你真正掌握这个"简单却容易出错"的算法。

二分查找的核心思想

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它的核心思想非常直观：每次将搜索区间减半，直到找到目标或确定目标不存在。

假设你在一本字典中查找一个单词，最愚蠢的方法是从第一页开始逐页翻阅；聪明的做法是翻开字典中间，根据目标单词与当前页首字母的大小关系，决定继续在前半部分还是后半部分查找。这就是二分查找的本质——利用有序性快速缩小搜索范围。

对于一个长度为 $n$ 的有序数组，二分查找的时间复杂度为 $O(\log n)$，空间复杂度为 $O(1)$。当 $n = 1,000,000$ 时，线性查找最坏需要 1,000,000 次比较，而二分查找最多只需要 $\log_2(1000000) \approx 20$ 次比较——效率提升 50,000 倍。

二分查找示意图

图片来源: GeeksforGeeks - Binary Search

标准二分查找模板

LeetCode 704 是二分查找最基础的题目：给定一个升序排列的整数数组和一个目标值，返回目标值在数组中的索引，如果不存在则返回 -1。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止溢出
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

这段代码看起来简单，但隐藏着几个容易出错的细节。

细节一：为什么用 left + (right - left) / 2 而不是 (left + right) / 2？

2006 年，Google 工程师 Joshua Bloch 发现了一个困扰业界 20 年的 bug。当 left 和 right 都很大时，left + right 可能超过 Integer.MAX_VALUE（$2^{31} - 1$），导致溢出变成负数。这个 bug 在《Programming Pearls》中的代码里也存在，直到数组大小超过 10 亿时才会触发——在 80 年代这是不可想象的，但在现代大数据场景下却很常见。

正确的写法有两种：

  • mid = left + (right - left) / 2：先做减法，避免溢出
  • mid = (left + right) >>> 1：使用无符号右移，即使溢出也能得到正确结果

细节二：循环条件为什么是 <= 而不是 <？

这取决于搜索区间的定义。使用 left <= right 时，搜索区间是闭区间 [left, right]，当 left == right 时区间内还有一个元素需要检查。如果使用 left < right，则搜索区间是左闭右开 [left, right)，当 left == right 时区间为空，会漏掉最后一个元素。

细节三：为什么更新边界时用 mid + 1 和 mid - 1？

因为我们已经检查了 nums[mid]，它不等于目标值，所以可以安全地排除。如果只写 left = mid 或 right = mid，在只剩两个元素时可能陷入死循环。

左边界查找：寻找第一个等于目标值的位置

很多时候，数组中可能有重复元素，我们需要找到目标值第一次出现的位置。这就是"左边界查找"，也称为"lower_bound"。

LeetCode 34 要求找到目标值在排序数组中的起始和结束位置。我们可以通过两次二分查找分别找到左右边界。

// 查找左边界：第一个 >= target 的位置
private int findLeftBound(int[] nums, int target) {
    int left = 0, right = nums.length;  // 注意：right 初始为 length
    
    while (left < right) {  // 注意：条件是 < 而不是 <=
        int mid = left + (right - left) / 2;
        
        if (nums[mid] >= target) {
            right = mid;  // 收缩右边界
        } else {
            left = mid + 1;
        }
    }
    
    // 检查是否找到目标值
    if (left == nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

这里的代码与标准二分查找有几个关键区别：

搜索区间变为左闭右开 [left, right)：right 初始为 nums.length 而不是 nums.length - 1，因为左边界可能是数组末尾的下一个位置（目标值比所有元素都大时）。

循环条件变为 left < right：当 left == right 时，区间 [left, right) 为空，循环结束。

nums[mid] >= target 时执行 right = mid：我们不是立即返回，而是继续向左收缩，直到找到最左边的位置。

最后需要验证：返回的 left 位置确实等于目标值。

右边界查找：寻找最后一个等于目标值的位置

右边界查找的逻辑与左边界对称，但有一个微妙的变化：

// 查找右边界：最后一个 <= target 的位置
private int findRightBound(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;
        }
    }
    
    // 检查是否找到目标值
    if (left == 0 || nums[left - 1] != target) {
        return -1;
    }
    return left - 1;  // 注意：返回 left - 1
}

为什么返回 left - 1 而不是 left？因为在循环中，当 nums[mid] <= target 时，我们执行 left = mid + 1，这意味着 left 最终指向的是第一个大于目标值的位置。所以右边界应该是 left - 1。

搜索插入位置：LeetCode 35

LeetCode 35 要求在有序数组中找到目标值的插入位置。如果目标值存在则返回其索引，否则返回它应该被插入的位置。

这其实就是左边界查找的简化版：

class Solution {
    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) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;  // 直接返回 left，无需验证
    }
}

无论目标值是否存在，left 都指向它应该插入的位置。

二分查找在答案空间上的应用

二分查找的威力远不止于在有序数组中查找元素。只要问题具有"单调性"，我们就可以对"答案空间"进行二分。这是二分查找最难但也最有价值的变体。

判断是否适用二分查找

如果一个问题的答案具有以下性质，就可以用二分查找：

  1. 答案是一个数值范围
  2. 对于答案 $x$，如果 $x$ 满足条件，那么所有 $\geq x$（或 $\leq x$）的值也满足
  3. 我们需要找到满足条件的最小（或最大）值

LeetCode 875: 爱吃香蕉的珂珂

珂珂有 $n$ 堆香蕉，每小时可以选择一堆吃掉 $k$ 根香蕉。如果一堆香蕉不足 $k$ 根，她吃完这堆后该小时不再吃其他堆。给定总时间 $h$，求最小的 $k$ 使得她能在 $h$ 小时内吃完所有香蕉。

这是一个典型的"二分答案"问题。我们不是在数组中查找，而是在吃香蕉速度 $k$ 的可能取值范围上进行二分：

  • 最小速度是 1（每小时吃 1 根）
  • 最大速度是最大堆的大小（一次吃掉任意一堆）

对于给定的速度 $k$，我们可以计算吃完所有香蕉需要的时间。如果时间 $\leq h$，说明 $k$ 足够大，可以尝试更小的速度；否则需要增大速度。

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (canFinish(piles, mid, h)) {
                right = mid;  // 能吃完，尝试更小的速度
            } else {
                left = mid + 1;  // 吃不完，需要更大的速度
            }
        }
        
        return left;
    }
    
    private boolean canFinish(int[] piles, int speed, int h) {
        int time = 0;
        for (int pile : piles) {
            time += (pile + speed - 1) / speed;  // 向上取整
        }
        return time <= h;
    }
}

LeetCode 69: x 的平方根

实现 int sqrt(int x)，返回 x 的平方根的整数部分。

这道题可以在 $[1, x]$ 范围内二分查找满足 $mid^2 \leq x$ 的最大值：

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        
        int left = 1, right = x;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // 使用除法避免 mid * mid 溢出
            if (mid <= x / mid) {
                if ((mid + 1) > x / (mid + 1)) {
                    return mid;  // mid 是最大的满足条件的值
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return right;
    }
}

旋转数组中的二分查找

旋转有序数组是二分查找的一个经典变体场景。数组原本有序，但在某个位置被旋转了，比如 [0,1,2,4,5,6,7] 旋转后变成 [4,5,6,7,0,1,2]。

LeetCode 153: 寻找旋转排序数组中的最小值

关键观察：旋转后，数组被分成两段有序的部分。最小值就是两段的分界点。

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] > nums[right]) {
                // 中间值大于右边界值，说明最小值在右半部分
                left = mid + 1;
            } else {
                // 中间值小于等于右边界值，说明最小值在左半部分（包括 mid）
                right = mid;
            }
        }
        
        return nums[left];
    }
}

LeetCode 33: 搜索旋转排序数组

这道题更复杂，需要在旋转数组中搜索目标值。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            
            // 判断哪一半是有序的
            if (nums[left] <= nums[mid]) {
                // 左半部分有序
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右半部分有序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return -1;
    }
}

核心思路是：虽然整个数组无序，但每次二分后，至少有一半是有序的。我们可以判断目标值是否在有序的那一半中，从而决定搜索方向。

旋转数组二分查找示意图

图片来源: LeetCode Discuss

寻找峰值：LeetCode 162

峰值元素是指其值严格大于左右相邻值的元素。给定一个数组，找到任意一个峰值并返回其索引。

这道题的妙处在于，数组不需要有序，但仍然可以用二分查找。关键观察是：如果 nums[mid] < nums[mid + 1]，那么 mid 右边一定存在峰值；反之，mid 左边（包括 mid 本身）一定存在峰值。

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] < nums[mid + 1]) {
                // 上坡，右边一定有峰值
                left = mid + 1;
            } else {
                // 下坡，左边（包括 mid）一定有峰值
                right = mid;
            }
        }
        
        return left;
    }
}

这个算法的正确性基于一个数学事实：对于任何数组，只要 nums[0] > nums[-1]（虚拟边界）且 nums[n] > nums[n-1]（虚拟边界），就一定存在峰值。当我们向高处移动时，最终一定会到达某个峰值。

二分查找的时间复杂度分析

二分查找每次将搜索空间减半，设初始搜索空间大小为 $n$，经过 $k$ 次迭代后搜索空间变为 1：

$$\frac{n}{2^k} = 1 \implies k = \log_2 n$$

因此时间复杂度为 $O(\log n)$。

相比之下，线性查找的时间复杂度是 $O(n)$。当 $n$ 很大时，这个差距是巨大的：

n 线性查找（最坏） 二分查找（最坏）
10 10 4
1,000 1,000 10
1,000,000 1,000,000 20
1,000,000,000 1,000,000,000 30

LeetCode 二分查找题目分类

根据不同的应用场景，LeetCode 上的二分查找题目可以分为以下几类：

基础二分查找

  • 704. Binary Search：标准二分查找
  • 35. Search Insert Position：搜索插入位置（左边界变体）
  • 374. Guess Number Higher or Lower：猜数字游戏

边界查找

  • 34. Find First and Last Position：找左右边界
  • 278. First Bad Version：找第一个错误版本（左边界）

答案空间二分

  • 69. Sqrt(x)：平方根
  • 875. Koko Eating Bananas：最小吃香蕉速度
  • 1011. Capacity To Ship Packages：最小运输容量
  • 410. Split Array Largest Sum：分割数组最大和

旋转数组

  • 33. Search in Rotated Sorted Array：搜索旋转数组
  • 81. Search in Rotated Sorted Array II：有重复元素的旋转数组
  • 153. Find Minimum in Rotated Sorted Array：找最小值
  • 154. Find Minimum in Rotated Sorted Array II：有重复元素

其他变体

  • 162. Find Peak Element：找峰值
  • 4. Median of Two Sorted Arrays：两个有序数组的中位数（困难）
  • 300. Longest Increasing Subsequence：最长递增子序列（二分优化）

为什么二分查找如此容易写错

回到文章开头的问题：为什么 90% 的程序员写不对二分查找？

边界条件是最常见的错误来源：

  • left <= right 还是 left < right？
  • right = nums.length 还是 right = nums.length - 1？
  • right = mid 还是 right = mid - 1？
  • 返回 left 还是 left - 1？

这些问题没有统一答案，取决于具体的搜索区间定义和问题要求。理解原理比死记模板更重要。

整数溢出是隐藏的陷阱： 即使逻辑正确，mid = (left + right) / 2 在大数据情况下也会出错。这个 bug 存在了 20 年才被发现。

死循环是常见的 bug： 当只剩一两个元素时，边界更新不当会导致死循环。比如只写 left = mid 而不是 left = mid + 1。

写出正确二分查找的建议

  1. 明确搜索区间：是闭区间 [left, right] 还是左闭右开 [left, right)？
  2. 确定循环条件：闭区间用 <=，左闭右开用 <。
  3. 正确更新边界：确保每次迭代都能缩小搜索空间。
  4. 处理边界情况：空数组、单元素数组、目标值不存在等。
  5. 验证结果：对于边界查找，需要验证返回值是否确实等于目标。

二分查找看似简单，实则细节众多。正如 Knuth 所说：“虽然第一个二分查找发表于 1946 年，但第一个正确的实现直到 1962 年才出现。“理解这些细节，才能在面试中游刃有余地应对各种二分查找变体。