二分

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

目标 - > 找到第一个 T

1
2
3
4
5
6
7
8
9
10
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;
}
// [lo, hi]闭区间内，寻找第一个match的值

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);

统计频率可以用unordered_map来预处理，再灵活运用stl函数求边界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// leetcode 2080
class RangeFreqQuery {
public:
    unordered_map<int, vector<int>> pos;
    RangeFreqQuery(vector<int>& arr) {
        for (int i = 0; i < arr.size(); i++) 
            pos[arr[i]].push_back(i);
    }
    int query(int left, int right, int value) {
        auto& v = pos[value];
        auto l = lower_bound(v.begin(), v.end(), left);
        auto r = upper_bound(v.begin(), v.end(), right);
        return r - l;
    }
};

灵活使用lower_bound和upper_bound

1
2
3
4
// left <= x <= right
auto l = lower_bound(v.begin(), v.end(), left);
auto r = upper_bound(v.begin(), v.end(), right);
return r - l;