二分搜索

发布于2021-02-02

上次编辑2021-02-27

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

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

int 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

返回顶部

在手机上阅读