二分

  • 答案区间 [LOW, HIGH]
  • 函数 f(x) -> {F, T}
  • 两级分布 F,F,F...F,T,T,T,...T

目标 - > 找到第一个 T

1
2
3
4
5
6
7
8
9
template <typename T, typename M>
T get_first_match(T lo, T hi, M match) {
    while (lo <= hi) {
        T mid = lo + (hi - lo) / 2;
        if(match(mid)) hi = mid - 1;
        else lo = mid + 1;
    }
    return lo;
}

binary_search(vec.begin(), vec.end(), target)检查有序数组中是否包含target，返回值是true or false

lower_bound(vec.begin(), vec.end(), target) - vec.begin();计算出目标下标

lower_bound -> 第一个大于等于 upper_bound -> 第一个大于

二分答案：（直接求解困难）：函数两极性 - -> 判断答案是否满足

实数二分终止条件：范围小于epsilon(const double eps = 1e-6)

特征：找符合xx条件的最大或者最小值

例子：最多将数组分成M组，每组之和不超过X，求X的最小值

  • 枚举将N个元素最多划分为M组的各个方案
  • 计算每组的和，取各组的最大值，然后取所有方案的最小值

转化为 —>

  • 确定每组的最大值X
  • 判断在X的限制下，是否可以划分为M组
1
2
int lo = *max_element(vec.begin(), vec.end());
int hi = accumulate(vec.begin(), vec.end(), 0);