Binary Search

二分在做什么

二分的本质不是"在有序数组里找数",而是:

在一个单调的判定函数上,用O(log⁡n)O(\log n) 次询问定位分界点。

把问题看成:有一个序列 [false, false, ..., false, true, true, ..., true](或反过来),要找最后一个 false / 第一个 true。

     找第一个 true
     ▼
F F F F T T T T T
0 1 2 3 4 5 6 7 8
        ↑
      答案

这个视角统一了所有二分变体。

在有序数组中查找(lower_bound / upper_bound)

C++ STL 的两个语义,背下来:

函数含义返回
lower_bound(beg, end, v)第一个≥v\ge v 的位置若不存在则 end
upper_bound(beg, end, v)第一个>v> v 的位置若不存在则 end
// a = [1, 2, 2, 2, 3]
lower_bound(a, 2)  → 下标 1   (第一个 2)
upper_bound(a, 2)  → 下标 4   (第一个 3)
// [lower, upper) 就是值为 2 的区间:[1, 4),共 3 个

由此得到常用组合:

// 计数:有几个 v
int cnt = upper_bound(a, v) - lower_bound(a, v);

// 是否存在 v
bool exist = lower_bound(a, v) != a.end() && *lower_bound(a, v) == v;

// 前驱(< v 的最大值)
auto it = lower_bound(a, v);
if (it != a.begin()) --it;    // 此时 *it < v

// 后继(> v 的最小值)
auto it = upper_bound(a, v);  // *it > v

手写的两种写法

写法一:闭区间 [l, r](推荐,最清晰)

// 找第一个 >= v 的位置(lower_bound)
int l = 0, r = n - 1, ans = n;   // ans 初始为"不存在"
while (l <= r) {
    int m = l + (r - l) / 2;     // 防溢出,别写 (l+r)/2
    if (a[m] >= v) {
        ans = m;                 // m 可行,先记下来
        r = m - 1;               // 再往左找更优的
    } else {
        l = m + 1;
    }
}

要点:

  • 循环条件 l <= r
  • 移动时 m ± 1(必须跨过 m,否则死循环)
  • 用 ans 记录可行解,循环自然结束时 ans 就是答案
  • m = l + (r-l)/2 而不是 (l+r)/2,避免 l+r 溢出(虽然 int 场景下少见,但养成习惯)

写法二:左闭右开 [l, r)

// 找第一个 >= v 的位置
int l = 0, r = n;                // r 是开区间端点,取 n
while (l < r) {
    int m = l + (r - l) / 2;
    if (a[m] >= v) r = m;        // [l, m)
    else           l = m + 1;    // [m+1, r)
}
// 循环结束时 l == r,就是答案

要点:

  • 循环条件 l < r
  • 缩右边界时 r = m(不减 1,因为右开)
  • 结束时 l == r,直接就是答案,不需要额外 ans

两种写法选一个用熟即可。混用是最常见的 bug 来源。

二分答案

当问题问"最大的最小值""最少需要多少时间""最多能装多少"时,考虑二分答案。

模板

// 求满足条件的最大 x
bool check(int x) {
    // 判定 x 是否可行(通常是个贪心/模拟,O(n))
}

int l = lo, r = hi, ans = lo;
while (l <= r) {
    int m = l + (r - l) / 2;
    if (check(m)) {
        ans = m;
        l = m + 1;      // 可行 → 试试更大的
    } else {
        r = m - 1;      // 不可行 → 只能更小
    }
}

关键:check(x) 必须对 x 单调——x 可行则所有更小的也可行(或反过来)。

经典例子:木材切割

n 根木头,长度 L[i],要切出 k 段等长的小段,求最大长度。

bool check(int len) {
    if (len == 0) return true;
    long long cnt = 0;
    for (int x : L) {
        cnt += x / len;
        if (cnt >= k) return true;   // 提前退出,防溢出
    }
    return cnt >= k;
}

// 答案越大,能切出的段数越少 → 单调 → 可二分
int l = 1, r = *max_element(L.begin(), L.end()), ans = 0;
while (l <= r) {
    int m = l + (r - l) / 2;
    if (check(m)) ans = m, l = m + 1;
    else          r = m - 1;
}

单调性:lenlen 增大 → 每段更长 → 切出的段数更少。所以"能切出≥k\ge k 段"这个性质对lenlen 单调(小的时候成立,大的时候不成立)→ 找最大的满足条件的lenlen。

二分答案的识别信号

题目措辞二分什么
"最大值最小" / "最小化最大值"二分那个"值"
"最少需要几天"二分天数
"最多能装多少"二分容量
"第 k 小"有时可二分值(配合计数)

二分查找的三类变体

1. 找精确值

int l = 0, r = n - 1;
while (l <= r) {
    int m = l + (r - l) / 2;
    if      (a[m] == v) return m;
    else if (a[m] <  v) l = m + 1;
    else                r = m - 1;
}
return -1;

2. 找边界(lower/upper bound)

见上文。

3. 在答案上二分(实数域)

// 求 sqrt(2),精度 1e-8
double l = 0, r = 2;
for (int i = 0; i < 100; i++) {      // 固定迭代次数,别用 while(l<r)
    double m = (l + r) / 2;
    if (m * m < 2) l = m;
    else           r = m;
}
printf("%.8f\n", l);

实数二分不要用 while (l < r)——浮点比较会有精度问题导致死循环。用固定迭代次数(100 次足够把区间缩到2−1002^{-100},远超 double 精度)。

4. 旋转排序数组

[4,5,6,7,0,1,2](在某个点旋转过的有序数组)中查找。

int search(vector<int>& a, int target) {
    int l = 0, r = a.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == target) return m;
        if (a[l] <= a[m]) {          // 左半有序
            if (a[l] <= target && target < a[m]) r = m - 1;
            else                                 l = m + 1;
        } else {                     // 右半有序
            if (a[m] < target && target <= a[r]) l = m + 1;
            else                                 r = m - 1;
        }
    }
    return -1;
}

思路:m 把数组分成两半,必有一半是有序的,在有序的那一半里判断 target 是否落入。

有重复元素时([2,2,2,0,2,2]),a[l] <= a[m] 的判断会失效,需要 if (a[l] == a[m]) l++; 跳过,最坏退化到O(n)O(n)。

C++ 标准库相关

// 有序容器自带
std::set<int> s;
s.lower_bound(v);   // 第一个 >= v 的迭代器
s.upper_bound(v);   // 第一个 >  v 的迭代器

// 无序数组要先排序
sort(a.begin(), a.end());
auto it = lower_bound(a.begin(), a.end(), v);
int idx = it - a.begin();

// 自定义比较(注意:比较函数必须和排序时用的一致)
lower_bound(v.begin(), v.end(), key,
            [](const Item& a, int k) { return a.k < k; });

复杂度

T(n)=T(n/2)+O(1)=O(log⁡n)T(n) = T(n/2) + O(1) = O(\log n)

二分答案时总复杂度是:

O(log⁡(值域)×check 的复杂度)O(\log(\text{值域}) \times \text{check 的复杂度})

例:值域10910^9,check 是O(n)O(n),n=105n = 10^5 →30×105=3×10730 \times 10^5 = 3 \times 10^7,可接受。

注意:如果 check 是O(n2)O(n^2),二分答案可能比直接做还慢。先算总复杂度再决定。

常见坑

  • (l + r) / 2 溢出:l、r 接近 INT_MAX 时溢出。用 l + (r - l) / 2
  • 死循环:l = m 而没 +1,且 m = (l+r)/2 向下取整,当 r = l+1 时 m = l → 无限循环。必须保证区间每次都严格缩小
  • 边界初始化错:ans 应该初始化为"确定不可行的值"还是"确定可行的值"?取决于你找的是最大还是最小
  • lower_bound vs 手写不一致:手写时用 a[m] >= v 才是 lower_bound,写成 > 就是 upper_bound 了
  • 忘了排序:对无序数组用二分,结果随机
  • 单调性不成立就二分:比如"是否存在长度为 k 的上升子序列"对 k 是单调的,但"第 k 大的元素所在位置"就不一定
  • 实数二分的终止条件:用固定迭代次数,不要 while (l < r) 或 while (r - l > eps)(后者在 eps 太小且 double 精度不够时死循环)
  • 二分答案的值域范围:r 取太小会漏解。宁可开大一点(比如取 max_element 而不是 sum/n)