二分查找有个著名的梗：“一看就会，一写就错”。

甚至有人统计过，能一次写对二分查找的工程师不到 20%。

问题几乎全出在一个地方：边界条件。今天把它彻底讲透。

二分查找的前提

二分查找只能用于有序数组（或单调序列）。

它的核心思想：每次取中间值，和目标比大小，直接排除一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(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，这在 left 和 right 都很大时会整数溢出（超过 int 最大值）。

left + (right - left) / 2 等价于 (left + right) / 2，但避免了溢出。

这是细节，但体现功底。

细节二：左闭右闭 vs 左闭右开

二分查找最容易乱的地方，是区间的定义。你必须在一开始就明确：

区间是”左闭右闭 [left, right]”，还是”左闭右开 [left, right)”？

这两种定义，导致循环条件、更新方式完全不同。

左闭右闭 [left, right]

  • 循环条件：left <= right（left == right 时区间还有 1 个元素，需要判断）
  • 更新：left = mid + 1，right = mid - 1

左闭右开 [left, right)

  • 循环条件：left < right（left == right 时区间为空，该退出了）
  • 更新：left = mid + 1，right = mid（因为 right 本身不包含）

90% 的二分查找 bug，都是因为区间定义和更新方式没对上。

我的建议：选定一种定义（推荐左闭右闭），然后严格保持一致，别混用。

进阶：找左右边界

上面是最基本的”查找目标值”。但实际中常常要查”目标值的左右边界”，比如：

在 [1, 2, 2, 2, 3] 中找 2 的最左位置和最右位置。

找左边界（第一个 >= target 的位置）

1
2
3
4
5
6
7
8
9
10
11
12
int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length; // [left, right)
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;  // 相等时也收缩右边界，逼近最左
        }
    }
    return left;
}

关键：即使 nums[mid] == target，也收缩右边界，这样才能不断逼近最左的位置。

找右边界（最后一个 <= target 的位置）

对称地，找到”第一个 > target 的位置”再减 1，或者用对称写法。

为什么二分查找这么容易错

根本原因：边界和”等于”的处理，稍微一变就全错。

应对方法其实就三条：

  1. 明确区间定义（闭 or 开），并保持一致
  2. 画个图，模拟一遍 mid、left、right 怎么移动
  3. 用测试用例兜底，尤其测边界（空数组、单元素、目标不存在、目标在两端）

二分查找的广泛应用

二分查找不只是”在数组里找数字”，它的思想——每次排除一半——应用极广：

  • 求平方根
  • 在”答案范围”上二分（如”最小化最大值”类问题）
  • 查找旋转排序数组中的元素
  • 数据库 B+ 树索引的查找

写在最后

二分查找是检验基本功的”照妖镜”：它逻辑简单，却极其考验对边界和细节的把控。

能把二分查找一次写对，并且讲清楚左闭右开和左闭右闭的区别，基本就能证明你的算法基础是扎实的。

下一篇讲递归与回溯——另一个”看起来简单、写起来要命”的主题。