二分查找（Binary Search）大概是每个程序员最早接触到的算法之一：在有序数组里找目标值，每次砍掉一半，O(log n) 完事。听起来简单到不值一提。但只要稍微写过几道二分题，几乎所有人都经历过「改一个符号就死循环」「差一行就越界」「边界永远是 off-by-one」的折磨。Donald Knuth 在《The Art of Computer Programming》里指出，第一个正确的二分查找算法直到 1962 年才被发表——而在此之前的十多年里，流传的版本大多是错的。直到 2006 年，Google 的 Joshua Bloch 还在 Java 标准库的 Arrays.binarySearch 里发现了一个隐藏了 9 年的整数溢出 bug。

这篇教程不打算把二分当成「背模板」的事来处理。我们会从最本质的「二段性」出发，讲清楚为什么两种区间写法各自成立、循环不变量如何决定边界更新、lower_bound 与 upper_bound 究竟在做什么，再扩展到「二分答案」「浮点二分」这些工程与竞赛中的高频套路，最后系统梳理那些反复让人翻车的陷阱。读完之后，你应该能够在不依赖记忆模板的情况下，凭「循环不变量」推演出任何二分变体的正确写法。

一、二分的本质：单调性与二段性

很多人对二分查找的第一印象是「必须有序」。这个说法没错，但不准确，它会让初学者误以为二分只能用于数组这种线性结构、只能用来「找一个相等的值」。

真正支撑二分成立的，是一个更弱的性质，叫做二段性（也叫「判定函数的单调性」或「可二分性」）：

如果存在一个判定条件 check(x)，使得答案空间可以被它切成两段——一段 check 恒为真、另一段 check 恒为假（或反之），那么就可以用二分在 O(log n) 内找到这两段的分界点。

有序数组上的「精确查找」只是二段性的一个特例。设判定条件为 nums[mid] < target：

  • 在有序数组中，所有 nums[i] < target 的下标构成一个前缀，所有 nums[i] >= target 的下标构成一个后缀。这天然就是两段。
  • 二分找的「分界点」就是首个 nums[i] >= target 的位置，也就是 lower_bound。
  • 至于「恰好等于 target」的精确查找，只是在分界点之上再做一次「是否相等」的检查。

把视角从「有序 + 相等」切换到「二段性 + 找分界点」，二分的应用范围就立刻打开了：

  • 单调函数求零点：f(x) 单调递增，f(l) 与 f(r) 异号，则 check(x) = f(x) < 0 满足二段性。
  • 二分答案：如果「答案越大越难满足」(单调的可行性函数)，那么 check(ans) = 可行 在答案轴上呈前缀真、后缀假，分界点就是最大可行答案。
  • 旋转排序数组：虽然整体无序，但在 mid 切开后，至少有一半是单调的，可以在那一半上建立二段性判断。
  • 求凸函数极值（三分查找的近亲）：虽然不是严格二分，但思想同源——利用「单峰性」做对数级剪枝。

记住一句话：不要问「这个数组有没有序」，要问「我能不能定义一个 check，让答案空间被它切成两段」。 能，就能二分。

二、正确性直觉与循环不变量

二分代码之所以脆弱，根因在于它的每一步都依赖一个循环不变量（loop invariant）——一个在循环开始、每次迭代前后都成立的断言。一旦不变量被某次更新悄悄破坏，立刻就是死循环或越界。

2.1 mid 的取法与溢出

最朴素的写法 mid = (left + right) / 2 在 left + right 超过 int 上界时会溢出。Joshua Bloch 修的那个 Java bug 就是把它换成：

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

或者更直观、且对负数也安全的位运算写法：

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

注意 >> 在有符号整数上是算术右移，对负数仍然正确。但 right - left 在我们的不变量下永远非负，所以两种写法等价。后者的好处是清晰表达「先算跨度，再取一半」的意图。

另一个细节：当区间长度为偶数时，left + (right - left) / 2 取的是偏左的中点。这一点在「左闭右开」写法里至关重要——它保证了 mid 永远严格小于 right（只要 left < right），从而让 right = mid 不会陷入死循环。如果改成偏右中点 mid = left + (right - left + 1) / 2，配合 right = mid 就会卡死。这就是后面会反复出现的「中点取法与区间收缩方向必须配套」原则。

2.2 三种二分变体的不变量

理解二分最快的办法是同时盯住三件事：

  1. 区间语义：[left, right] 还是 [left, right)？这决定了 while 条件用 <= 还是 <。
  2. 收缩方向：当 nums[mid] 与 target 满足某个关系时，是丢掉左半还是右半？这决定了 left = mid + 1 还是 right = mid - 1（或 right = mid）。
  3. 终止时的指针位置：循环结束时 left 与 right 的关系是什么？答案落在哪个指针上？

只要这三者自洽，代码就是对的。后面每一节，我们都会显式地把这三件事摆出来。

三、算法框架：两种区间写法

二分查找在工业界和教材里主要有两种等价写法，差别只在「区间是闭还是半开」。它们都能写出正确的代码，但风格不同，混用是 bug 的最大来源之一。强烈建议固定一种写法练到肌肉记忆，另一种只用于读别人的代码。

3.1 左闭右闭 [left, right]

这是国内教材和 LeetCode 题解最常见的写法。区间包含两端，所以：

  • while (left <= right)：当 left == right 时区间里还有一个元素，需要继续检查。
  • 收缩时两端都跳过 mid：left = mid + 1 或 right = mid - 1。因为 mid 已经被检查过了，不应再留在区间里。
  • 终止时 left == right + 1，区间为空。
1
2
3
4
5
6
7
8
9
10
11
// 左闭右闭模板：在升序数组中找 target 的任意一个出现位置
int binarySearchClosed(const std::vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size() - 1;   // [left, right]
    while (left <= right) {                        // 区间非空
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;   // [mid+1, right]
        else                          right = mid - 1; // [left, mid-1]
    }
    return -1;
}

不变量：「target 若存在，必在 [left, right] 内」。每次更新都把 mid 排除在外，所以区间严格缩小，必然终止。

3.2 左闭右开 [left, right)

这是 STL、C++ 标准库、《编程珠玑》和大多数函数式语言偏好的写法。区间不含右端点：

  • while (left < right)：当 left == right 时区间为空，停止。
  • 收缩时左端跳过 mid，右端不跳：left = mid + 1（mid 已检查），right = mid（mid 本就不在区间内）。
  • 终止时 left == right，二者都指向「插入位置」。
1
2
3
4
5
6
7
8
9
10
11
// 左闭右开模板：返回 target 的下标，不存在则返回应插入的位置
int binarySearchHalfOpen(const std::vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size();       // [left, right)
    while (left < right) {                         // 区间非空
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;  // [mid+1, right)
        else                          right = mid;     // [left, mid)
    }
    return left;  // 不存在时，left 即插入位置
}

不变量：「target 若存在，必在 [left, right) 内」。

3.3 两种写法的取舍

维度左闭右闭 [l, r]左闭右开 [l, r)
初始化right = n - 1right = n
循环条件left <= rightleft < right
right 更新right = mid - 1right = mid
终止态left = right + 1left == right
空区间天然处理需 n == 0 特判right = 0 自动成立
与 STL 一致性否是
找「插入位置」需要转换思考left 直接就是

实战建议：

  • 如果你要找「精确相等」且不存在返回 -1，左闭右闭直觉上更顺（right = mid - 1 把 mid 干干净净地排除掉）。
  • 如果你要做 lower_bound/upper_bound/二分答案这类「找分界点」的工作，左闭右开更省心——它直接复用 STL 的语义，终止时 left 就是答案，无需再判断 left 与 right 谁是谁。
  • 绝不要在同一段代码里混用两种风格。最经典的翻车是：初始化用 right = n - 1，循环里却写 right = mid，不变量立刻矛盾。

四、基础二分查找

这是二分最朴素的形式：在升序数组中找一个等于 target 的下标，找不到返回 -1。

示例：基础二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <vector>

int binarySearch(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 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;  // 未找到
}

思路：套用 3.1 的左闭右闭模板。不变量是「target 若存在必在 [left, right]」。

复杂度分析：

  • 时间：每次迭代区间至少减半，最坏 O(log n) 次；平均 O(log n)。
  • 空间：O(1)，迭代实现无递归栈。

变种与注意点：

  • 这个版本返回的是「任意一个」匹配下标，并不保证是第一次或最后一次出现。如果数组里有重复元素，比如 [1, 2, 2, 2, 3] 找 2，可能返回下标 1、2 或 3 中的任何一个。要保证返回最左/最右，必须改用下一节的边界查找。
  • 递归写法等价但栈深 O(log n)，在 n 极大时（如 10^9 上的二分答案）会爆栈，工程上几乎不用递归二分。
  • 标准库 std::binary_search 返回 bool，内部就是调用 std::lower_bound 再判等，并不返回下标。要下标请用 lower_bound 减去 begin()。

五、查找左边界与插入位置

5.1 查找左边界（首个等于 target 的位置）

当数组里有重复元素时，「精确二分」只能给出一个不确定的位置。很多时候我们需要的是第一个等于 target 的下标——这就是「左边界」。

示例：查找左边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <vector>

int findLeftBound(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // 检查边界
    if (left >= nums.size() || nums[left] != target) {
        return -1;
    }
    return left;
}

思路：这里的关键变化是 nums[mid] == target 时不立即返回，而是继续往左压：right = mid - 1。换言之，把「相等」和「大于」合并成同一个分支——「mid 及其右侧都不可能是左边界」。这样循环会一直把右端往左推，直到把所有等于 target 的元素都挤到区间右侧之外。

不变量变成：「首个 >= target 的位置（若存在）必在 [left, right] 内」。循环结束时 left == right + 1，而由于每次 right 都跳到 mid - 1，最终 left 恰好停在「首个 >= target」的位置上。

为什么是 left 而不是 right？ 想想终止条件 left = right + 1，意味着 left 比 right 多走了一步。left 一直被「nums[mid] < target」往右推，right 一直被「nums[mid] >= target」往左推。终止时 left 刚好越过 right，落在第一个满足 >= target 的位置。right 则落在「最后一个 < target」的位置。

复杂度：O(log n) 时间，O(1) 空间。

变种与优化：

  • 如果只关心「插入位置」而不关心是否真的等于 target，把末尾的检查去掉，直接 return left 即可——这正是 std::lower_bound 的语义。
  • 若 target 比所有元素都大，left 会停在 nums.size()，表示「应插到末尾」。这一点在插入场景下很重要，调用方需要处理越界。
  • 若 target 比所有元素都小，left 停在 0，正确。

5.2 用左闭右开改写：lower_bound 的标准实现

把上面的左闭右闭版本翻译成左闭右开，就得到了 STL std::lower_bound 的等价实现。注意 right 初始化为 nums.size()，且更新是 right = mid 而非 mid - 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <vector>

// 等价于 std::lower_bound：返回首个 >= target 的位置
int lowerBound(const std::vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size();   // [left, right)
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;   // mid 及左侧全部排除
        } else {
            right = mid;      // mid 仍可能是答案，保留
        }
    }
    return left;              // left == right，即插入位置
}

这里的不变量是「首个 >= target 的位置在 [left, right) 内」。当 left == right 时区间为空，left 就是指针最终落点。这个版本有一个微妙的优势：mid 永远严格小于 right（因为 left < right 且中点偏左），所以 right = mid 严格缩小区间，不会死循环。这是左闭右开写法在「找分界点」时格外稳的根本原因。

要得到「左边界」语义，只需在末尾加一次判等：

1
2
int idx = lowerBound(nums, target);
return (idx < (int)nums.size() && nums[idx] == target) ? idx : -1;

六、查找右边界

6.1 查找右边界（最后一个等于 target 的位置）

对称地，找最后一个等于 target 的下标，思路是「nums[mid] == target 时不返回，继续往右压」。

示例：查找右边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <vector>

int findRightBound(const std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // 检查边界
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

思路：这次把「相等」和「小于」合并——「mid 及其左侧都不可能是右边界」。left 一直被往右推，right 一直被往左推，最终 right 停在「最后一个 <= target」的位置，left 停在「首个 > target」的位置。所以右边界取 right。

复杂度：O(log n) 时间，O(1) 空间。

6.2 用左闭右开改写：upper_bound 的标准实现

注意右边界与 upper_bound（首个 > target 的位置）只差一个「判等后的回退」：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <vector>

// 等价于 std::upper_bound：返回首个 > target 的位置
int upperBound(const std::vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;   // mid 及左侧全部排除
        } else {
            right = mid;      // mid 仍可能是答案
        }
    }
    return left;              // 首个 > target 的位置
}

注意分支条件是 nums[mid] <= target（含等号），与 lowerBound 的 < 形成对比。这正是一字之差的精髓：lower_bound 把「等于」划进右段（要保留作为候选），upper_bound 把「等于」划进左段（要排除）。两者相减 upper_bound - lower_bound 就是 target 在数组中的出现次数，这就是 std::equal_range 的实现原理。

从 upperBound 反推「右边界」：右边界 = upperBound(nums, target) - 1，再判一次等即可：

1
2
int idx = upperBound(nums, target) - 1;
return (idx >= 0 && nums[idx] == target) ? idx : -1;

6.3 三种查找的对照表

把精确查找、左边界、右边界并排放，差异一目了然（左闭右闭版）：

查找目标nums[mid] < target 时nums[mid] == target 时nums[mid] > target 时终止后答案
精确（任一）left = mid + 1return midright = mid - 1-1（若未返回）
左边界left = mid + 1right = mid - 1right = mid - 1left（再判等）
右边界left = mid + 1left = mid + 1right = mid - 1right（再判等）

核心规律：「相等时往哪边压」决定了你找的是左边界还是右边界。往左压（right = mid - 1）找左边界，往右压（left = mid + 1）找右边界，立刻返回找任意一个。记住这个对应关系，就不需要死记三套模板。

七、二分答案：在值域上二分

到目前为止我们都在「下标空间」上二分。但二分真正强大的地方在于：只要能定义一个单调的可行性函数 check，就可以在「答案值域」上二分，把「求最优解」转化成「判定可行性」。这类问题统称「二分答案」，是竞赛与工程里最高频的二分应用之一。

二分答案的一般框架：

  1. 确定答案的取值范围 [L, R]（通常由题意给出，可能是下标、距离、时间、容量等）。
  2. 设计 check(x)：在假定答案为 x 的前提下，判断题意条件是否可满足。check 应满足单调性——x 越大（或越小）越难满足。
  3. 在 [L, R] 上二分，找到使 check 为真的最大（或最小）x。

关键在于：check 的实现往往是一个贪心或 DP，复杂度 O(n) 量级；二分套在外层 O(log R) 次，总复杂度 O(n log R)。 把指数级或 NP 难的「构造最优解」转化为多项式的「判定」，是二分答案的精髓。

7.1 二分答案（寻找平方根）

先看一个经典的「在值域上二分」的例子：给定非负整数 x，求 floor(sqrt(x))（即整数平方根）。

示例：二分答案（寻找平方根）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>

int mySqrt(int x) {
    if (x < 2) return x;
    
    int left = 1, right = x / 2;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        long long square = (long long)mid * mid;
        
        if (square == x) {
            return mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;  // right 是最后一个满足 mid^2 <= x 的值
}

思路：这里 check(mid) 就是「mid * mid <= x」。它是单调的——mid 越大越可能不满足。我们其实在做「找最后一个满足 mid^2 <= x 的 mid」，也就是右边界。所以循环结束后取 right，正好是「最后一个可行解」。

注意几个细节：

  • right 初始化为 x / 2 而非 x：因为对 x >= 2，sqrt(x) <= x / 2，缩小值域。x < 2 直接返回 x 处理 0 和 1 的边界。
  • (long long)mid * mid 必须先转型再相乘，否则 int 相乘会溢出。这是整数二分里最常见的隐藏 bug。
  • 终止时 left = right + 1，right 是最后一个满足条件的值，left 是第一个不满足的值。

复杂度：值域 [1, x/2]，二分 O(log x) 次，每次 O(1)，总计 O(log x)。

7.2 最大化最小值：放置牛棚

二分答案最经典的一类题型是「最大化最小值」或「最小化最大值」。题面通常形如「将 N 个东西分成 K 份，最大化每份的最小值」「放置 C 头牛到 N 个牛棚，最大化相邻牛的最小距离」。

题目（POJ 2456 Aggressive cows）：在一条直线上有 N 个牛棚，位置为 stalls[i]（已排序）。把 C 头牛放进其中 C 个牛棚，使得「任意两头牛的最近距离」尽可能大。求这个最大距离。

思路：

  • 答案空间是 [1, stalls[N-1] - stalls[0]]。
  • check(gap)：能否以「任意相邻牛距离 >= gap」的方式放置 C 头牛？这是一个贪心——把第一头牛放在最左边的牛棚，之后每头牛都放在「离上一头至少 gap」的最近牛棚，看能否放下 C 头。
  • 单调性：gap 越大越难放下，所以 check 在 gap 上呈前缀真、后缀假。我们要「最后一个为真的 gap」，即右边界。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <vector>
#include <algorithm>

// 判定：能否以间距至少为 gap 放置 C 头牛
bool canPlace(const std::vector<int>& stalls, int C, int gap) {
    int count = 1;          // 第一头牛放在 stalls[0]
    int last = stalls[0];
    for (int i = 1; i < (int)stalls.size(); ++i) {
        if (stalls[i] - last >= gap) {
            ++count;
            last = stalls[i];
            if (count >= C) return true;
        }
    }
    return count >= C;
}

int maxMinDistance(std::vector<int>& stalls, int C) {
    std::sort(stalls.begin(), stalls.end());
    int left = 1, right = stalls.back() - stalls.front();
    int ans = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canPlace(stalls, C, mid)) {
            ans = mid;          // mid 可行，尝试更大
            left = mid + 1;
        } else {
            right = mid - 1;    // mid 不可行，缩小
        }
    }
    return ans;
}

关键点：

  • check 是贪心，正确性证明：如果存在一种放法使最小间距 >= gap，那么「把每头牛尽量往左放」也一定可行（因为越往左放，留给后面的空间越大）。所以贪心不会错过可行解。
  • 二分写的是左闭右闭的「找右边界」模式：可行时记下 ans 并向右推，不可行时向左缩。也可以不显式记 ans，直接 return right，效果相同。
  • 「最大化最小值」永远对应「找最后一个可行解 = 右边界」；「最小化最大值」则对应「找第一个可行解 = 左边界」。这个对应关系记住，可以省去很多思考。

复杂度：排序 O(N log N)，二分 O(log(stalls.back())) 次，每次 check 是 O(N)，总计 O(N log N + N log R)，其中 R 是值域大小。

7.3 最小化最大值：切木头

对称的「最小化最大值」例子：给定 N 段木头长度，要切出 K 段等长的小木块，求小木块长度最大能是多少。

思路：

  • 答案空间 [1, max(woods)]。
  • check(len)：以长度 len 切，能否切出至少 K 段？check = sum(woods[i] / len) >= K。
  • 单调性：len 越大越难切够，check 呈前缀真、后缀假。这次要「最后一个为真的 len」——咦，也是右边界？

这里有个微妙之处：题目说「最大化长度」其实仍是「最大化最小值的变体」。真正「最小化最大值」的典型例子是「把数组分成 M 段，使各段和的最大值最小」——这类问题里答案单调性方向相反，要找左边界。所以判断方向时不要套题型名字，而要直接看 check 的单调性与所求：

  • check 越大越难为真 → 求「最大可行」 → 右边界 → 收缩时可行则向右、不可行则向左。
  • check 越大越易为真 → 求「最小可行」 → 左边界 → 收缩时可行则向左、不可行则向右。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
#include <algorithm>

// 以长度 len 切割，能否得到至少 K 段
bool canCut(const std::vector<int>& woods, int K, int len) {
    long long total = 0;
    for (int w : woods) total += w / len;
    return total >= K;
}

int maxLength(std::vector<int>& woods, int K) {
    int left = 1, right = *std::max_element(woods.begin(), woods.end());
    int ans = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canCut(woods, K, mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

注意 total 用 long long 防止 N * max_len 溢出。这是整数二分答案里第二个高频溢出点：check 内部的累加也要考虑大数。

八、浮点二分

当答案不是整数而是浮点数（求方程根、几何上的二分等），二分仍然适用，但需要处理「精度」与「终止条件」两个新问题。

8.1 经典模板：求单调函数的零点

设 f(x) 在 [lo, hi] 上单调递增，且 f(lo) * f(hi) < 0（异号），求 f(x) = 0 的根。

1
2
3
4
5
6
7
8
9
10
11
12
// 求方程 f(x) = 0 在 [lo, hi] 上的根（f 单调，f(lo) 与 f(hi) 异号）
double solve(double (*f)(double), double lo, double hi) {
    for (int i = 0; i < 100; ++i) {   // 固定迭代次数，规避精度判断
        double mid = (lo + hi) / 2;
        if (f(mid) * f(lo) <= 0) {
            hi = mid;                 // 根在 [lo, mid]
        } else {
            lo = mid;                 // 根在 [mid, hi]
        }
    }
    return (lo + hi) / 2;
}

思路：每次取中点，根据 f(mid) 的符号决定根在左半还是右半。注意浮点二分里 left = mid 而非 mid + 1——因为浮点没有「下一个」的概念，mid 本身就可能是答案。

为什么用固定 100 次迭代而不是 while (hi - lo > eps)？ 这是浮点二分的一个重要工程经验：

  1. 稳定性：eps 判据在某些情况下（比如根附近的函数值变化极陡）会让循环提前退出或永远不退出。固定迭代次数则保证：每次区间减半，100 次迭代后区间宽度为 (hi - lo) / 2^100，对任何合理的初始区间都远小于 double 的机器精度（约 2^-52），结果必然收敛。
  2. 可分析：迭代次数直接决定精度，log2((hi - lo) / eps) 次即可达到 eps 精度。100 次对几乎所有应用都过剩，但开销极小（每次 O(1)），可以放心写。
  3. 规避 eps 陷阱：eps 选太小（如 1e-12）可能因浮点误差永远达不到，选太大（如 1e-4）可能精度不够。固定迭代次数彻底回避这个权衡。

变种与注意点：

  • 如果 f 不是严格单调（比如有平台段），f(mid) * f(lo) <= 0 的 <= 让算法仍能找到一个根，但不保证唯一性。
  • 求 n 次方根（如立方根）可以套这个模板，令 f(x) = x^n - a。
  • 涉及几何（如「求两圆最近距离」「切线问题」）时，先把问题归约为「在某个参数区间上找一个单调函数的零点或极值」，再用浮点二分。

8.2 浮点二分答案：最大化最小距离（实数版）

回到 7.2 的牛棚问题，如果牛棚位置是浮点坐标，答案也是浮点数，只需把整数二分换成浮点二分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <vector>
#include <algorithm>

bool canPlace(const std::vector<double>& stalls, int C, double gap) {
    int count = 1;
    double last = stalls[0];
    for (int i = 1; i < (int)stalls.size(); ++i) {
        if (stalls[i] - last >= gap) {
            ++count;
            last = stalls[i];
            if (count >= C) return true;
        }
    }
    return count >= C;
}

double maxMinDistance(std::vector<double>& stalls, int C) {
    std::sort(stalls.begin(), stalls.end());
    double lo = 0, hi = stalls.back() - stalls.front();
    for (int i = 0; i < 100; ++i) {
        double mid = (lo + hi) / 2;
        if (canPlace(stalls, C, mid)) lo = mid;   // 可行，向右推
        else                          hi = mid;
    }
    return (lo + hi) / 2;
}

整数二分里「可行时 left = mid + 1」的 +1 在浮点版里消失——同样因为浮点没有「下一个」。

九、STL 二分族函数

C++ <algorithm> 提供了一整套二分工具，理解它们的语义和实现原理，可以避免重复造轮子，也能在调试时快速定位问题。

9.1 四个核心函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <vector>

std::vector<int> nums = {1, 2, 2, 2, 3, 5, 7};
int target = 2;

// lower_bound: 首个 >= target 的位置
auto lb = std::lower_bound(nums.begin(), nums.end(), target);  // 指向第一个 2

// upper_bound: 首个 > target 的位置
auto ub = std::upper_bound(nums.begin(), nums.end(), target);  // 指向 3

// equal_range: [lower, upper) 区间，即所有等于 target 的元素范围
auto [lo, hi] = std::equal_range(nums.begin(), nums.end(), target);

// binary_search: 是否存在（返回 bool）
bool found = std::binary_search(nums.begin(), nums.end(), target);

// 出现次数 = upper_bound - lower_bound
int count = ub - lb;   // 3

这四个函数都要求区间已经按升序排好。如果要降序，需要传自定义比较器：std::lower_bound(begin, end, target, std::greater<int>())，此时语义变为「首个 <= target 的位置」。比较器的一致性是另一个常见坑：lower_bound 用的比较器和排序用的比较器必须一致，否则结果未定义。

9.2 实现原理回顾

第五、六节已经给出了 lowerBound 和 upperBound 的实现。这里再补一个 equal_range 的等价实现，帮助理解它为什么是 O(log n) 而非两次 O(log n) 相加（实际上标准库的实现是单次二分里同时找两端，常数更优，但两次调用 lower_bound/upper_bound 的总复杂度仍是 O(log n)）：

1
2
3
4
5
6
7
8
#include <vector>
#include <utility>

std::pair<int, int> equalRange(const std::vector<int>& nums, int target) {
    int lo = lowerBound(nums, target);    // 首个 >= target
    int hi = upperBound(nums, target);    // 首个 > target
    return {lo, hi};                       // [lo, hi) 是所有 == target 的元素
}

9.3 为什么标准库用左闭右开

STL 全家桶都用迭代器区间 [first, last)，这是左闭右开。原因有几个：

  1. 空区间的天然表示：[first, first) 就是空，无需特判 first > last。左闭右闭要表达空区间得引入「无效值」或额外长度。
  2. 与指针/迭代器算术一致：last - first 直接给出元素个数；first + n 越过 last 时就是 last 本身，天然作为「找不到」的哨兵。
  3. 算法组合性：lower_bound 的返回值可以直接作为另一个 lower_bound 的 first，区间拼装无需 +1 调整。

理解了这一点，你就会明白为什么「找插入位置」用 STL 风格的左闭右开更顺手——它就是 STL 的母语。

十、横向对比

把前面散落的对比集中起来，方便复习。

10.1 两种区间写法的对照

操作左闭右闭 [l, r]左闭右开 [l, r)
right 初值n - 1n
while 条件l <= rl < r
right 更新r = mid - 1r = mid
mid 取法l + (r - l) / 2（偏左，安全）l + (r - l) / 2（偏左，必须）
终止态l = r + 1l == r
空数组处理需 n == 0 特判（right = -1 时 l <= r 不成立，循环不进，但取 nums[l] 会越界）天然安全（r = 0，l < r 不成立）
答案指针视情况取 l 或 rl 即 r，统一

10.2 三种查找目标的对照（左闭右闭）

目标== 分支终止答案等价 STL
精确（任一）return mid-1（若未返回）binary_search（返回 bool）
左边界right = mid - 1left，再判等lower_bound
右边界left = mid + 1right，再判等upper_bound - 1

10.3 二分答案的方向选择

check(x) 单调性求最优对应查找收缩策略
越大越难为真最大化可行 x右边界可行则 l = mid + 1，不可行则 r = mid - 1，记 ans = mid
越大越易为真最小化可行 x左边界可行则 r = mid - 1，不可行则 l = mid + 1，记 ans = mid

十一、实战场景

11.1 竞赛中的二分

  • 二分答案：几乎所有「最大化最小值」「最小化最大值」「最优解 + 单调性」的题。代表题：POJ 2456（牛棚）、洛谷 P1824、Codeforces 732D。判断标志：题目求最优 + 容易写出 O(n) 的可行性判定。
  • 二分 + 贪心/DP：check 内部往往是贪心（如牛棚的「尽量往左放」）或 DP（如「分成 M 段」的可行性）。二分只负责把答案空间压到对数级，重头戏在 check 的设计。
  • 二分 + 单调队列/栈：如「最长上升子序列」的 O(n log n) 解法，本质是「在长度维度上二分维护结尾最小值」。
  • 二分 + 二分图匹配（Hopcroft-Karp）：用 BFS 分层 + 二分找增广路。
  • 三分查找：求单峰函数极值。注意三分也有坑——平台段会让中点比较失效，需要谨慎处理。

11.2 工程中的二分

  • 数据库 B+ 树索引：每个节点内部用二分查找定位键。理解二分是理解索引的前提。
  • 内存分配器：glibc ptmalloc 的 bins、Linux 内核的伙伴系统都大量用二分或类似结构定位合适块。
  • C++ STL：std::sort（introsort 的快排退化阈值用二分确定）、std::lower_bound、std::binary_search、std::set/std::map 的红黑树节点内部查找。
  • 版本控制 bisect：git bisect 用二分在提交历史里定位引入 bug 的 commit，是二分思想在工程流程里的经典应用。
  • 数值计算：求根、求极值、二分搜索初始学习率（learning rate finder）。
  • HTTP/网络：TLS 握手时的 record layer 分片、拥塞控制的窗口探测都隐含二分思想。

工程上二分的一个常见变体是「二分 + 缓存友好」：由于 mid 跳跃访问破坏缓存局部性，对「几乎随机访问成本高」的结构（如磁盘、跨网络），会改用「指数二分」（galloping search）——先以 1, 2, 4, 8… 步长找上界，再在该区间内二分。Python 的 bisect、Linux 内核的 list_bisect 在某些场景下会启用这种优化。

十二、常见陷阱与边界条件

把这一节当成 checklist，每次写完二分都过一遍。

12.1 off-by-one：永远的头号杀手

表现形式：找到了但返回错位置、找不到时死循环、答案差 1。根因永远是「区间语义与更新方式不自洽」。

自检方法：手算两个极端用例——

  1. 单元素数组 nums = [5]，target = 5 和 target = 6 各跑一遍。
  2. 两元素数组 nums = [1, 3]，target = 0, 1, 2, 3, 4 各跑一遍。

这两个用例覆盖了「区间长度为 1 和 2」「mid 取偏左时」「目标比所有元素小/大/在中间」的所有分支。能跑通这 7 个用例，正确性基本有保证。

12.2 死循环：right = mid 配套错误

死循环几乎都源于「区间没有严格缩小」。典型场景：

1
2
3
4
// 错误：左闭右开却用偏右中点
int mid = left + (right - left + 1) / 2;  // 偏右
// ...
right = mid;  // 当 left == mid 时，区间不缩小，死循环

修复方案二选一：

  • 中点取偏左 mid = left + (right - left) / 2，配合 right = mid（左闭右开标准写法）。
  • 中点取偏右 mid = left + (right - left + 1) / 2，配合 left = mid（左闭右开找右边界的一种写法）。

原则：mid 必须严格不等于将被赋值的端点。具体说，如果用 right = mid，则 mid 必须严格小于 right（偏左中点保证）；如果用 left = mid，则 mid 必须严格大于 left（偏右中点保证）。这就是「中点取法与收缩方向必须配套」。

12.3 整数溢出：三处高危点

  1. mid 计算：(left + right) / 2 在 left + right > INT_MAX 时溢出。永远用 left + (right - left) / 2。
  2. check 内部的乘法：(long long)mid * mid、mid * 1LL * mid，必须先转型。int 乘 int 即便结果赋给 long long 也会先按 int 溢出再扩展。
  3. check 内部的累加：N 个元素各最大 M，累加用 int 在 N * M > INT_MAX 时溢出。统计类 check 默认用 long long。

12.4 空数组与越界

左闭右闭写法里，right = n - 1，当 n == 0 时 right = -1，left <= right 不成立，循环不进——看起来安全。但如果循环后直接 return nums[left]，left = 0 仍会越界。结论：循环后的指针访问必须有边界判断（left < n && nums[left] == target）。

左闭右开写法天然安全：right = 0，left < right 不成立，left = 0 也合法（就是「应插到开头」）。

12.5 重复元素与「任一」语义

如果数组有重复元素，且你用的是「精确二分」（== 时立刻返回），结果下标是「任一」而非「最左/最右」。在「统计出现次数」「找区间」类问题里这会出错。对策：明确语义，需要边界就用 lower_bound/upper_bound，不要用精确二分。

12.6 比较器不一致

std::lower_bound 用的比较器必须与排序用的比较器一致。sort 用 greater<int>() 降序排，lower_bound 也必须传 greater<int>()，否则结果未定义。同理，自定义结构体的二分要保证比较器与排序一致。

12.7 浮点二分的 eps 陷阱

  • while (hi - lo > eps) 在 eps 太小时可能因浮点精度永远达不到，陷入死循环。
  • f(mid) == 0 直接判等几乎永远不成立（浮点误差），应判 fabs(f(mid)) < eps 或改用符号比较 f(mid) * f(lo) <= 0。
  • 推荐：固定 100 次迭代，彻底回避 eps 选择。

12.8 二分答案的值域边界

  • left 必须是「一定可行」的下界，right 必须是「一定不可行」的上界（或反过来）。如果值域两端都可能可行/不可行，二分方向会错。
  • 经典错误：求「最大化最小距离」时 left = 0，但 gap = 0 永远可行且无意义，应从 1 开始。
  • 另一个：check(mid) 里 mid 可能除以 0（如 w / len 里 len = 0），需要保证值域不含 0 或特判。

十三、小结

二分查找的代码量小到只有十几行，但它的正确性完全建立在「循环不变量」之上。理解二分，不在于背下三套模板，而在于掌握一个推理流程：

  1. 明确区间语义：[l, r] 还是 [l, r)？这决定了 while 条件和 right 的更新。
  2. 明确查找目标：精确、左边界、右边界？这决定了「相等时往哪边压」。
  3. 明确收缩方向：丢左半还是右半？这决定了 left = mid + 1 还是 right = mid - 1（或 right = mid）。
  4. 明确终止答案：循环结束时 left 与 right 各指向什么？答案取哪个？是否需要判等？
  5. 验证不变量：每次更新后，原不变量是否仍成立？区间是否严格缩小？
  6. 过极端用例：空数组、单元素、两元素、目标比所有元素小/大/在中间。

掌握了这套流程，任何二分变体——不管是 lower_bound、upper_bound、二分答案、浮点二分、旋转数组二分，还是带自定义比较器的二分——都可以在不查模板的情况下现场推演出来。二分答案的关键则在于「把求最优解转成判定可行性」这一步思维转换：看到「最大化最小值」「最小化最大值」「求最大的 x 使条件成立」，本能反应就应该是「能不能二分答案」。

最后给一个忠告：写二分时，永远先写下你的区间语义和不变量，再写代码。 注释里写一句「target 若存在必在 [left, right] 内」看似多余，但它会在你犹豫 mid + 1 还是 mid 时救你一命。二分是少数几类「想清楚比写出来更重要」的算法——想清楚了，代码几乎是自明的；没想清楚，调一晚上也未必能过。