二分搜索

介绍

在区间上使用二分的前提是，当某个位置不满足条件时，那么所有比它小的位置（或者比它大的位置）都不满足条件。或者反过来说，当某个位置满足条件时，那么比它小的位置（或者比它大的位置）也都满足条件。

当问题是要求满足条件的最大值或者最小值时，可以考虑是否可以使用二分。

代码模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


auto ok = [&] (int M) -> bool {
    // Code here
};

int L, R; // 保证答案在 [L,R] 这个区间内

// 二分搜索满足条件的最小值
while (L < R) {
    auto M = L + ((R - L) >> 1);
    if (ok(M)) R = M;
    else L = M + 1;
}

// 二分搜索满足条件的最大值
while (L < R) {
    auto M = L + ((R - L + 1) >> 1);
    if (ok(M)) L = M;
    else R = M - 1;
}

库函数

区间非降序排列。

C++

#include <algorithm>

binary_search 区间是否存在某个数
lower_bound 第一个 大于等于 某个数的位置
upper_bound 第一个大于某个数的位置
equal_range 返回 pair 表示 lower_bound 和 upper_bound 分别搜索的结果

Python

from bisect import bisect_left, bisect_right

bisect_left 同 lower_bound
bisect_right 同 upper_bound

例题

https://leetcode.cn/tag/binary-search/problemset/