二分

二分查找

循环控制（必须要掌握）

//在有序的 a[1]~a[n] 中找到第一个大于等于 x 的位置
int l = 1;
int r = n;
int ans = n + 1;
while (l <= r)
{
    int mid = (l + r) / 2;
    if (a[mid] >= x)
    {
        ans = mid;
        r = mid - 1;
    }
    else
        l = mid + 1;
}

STL 的二分三兄弟

使用前必须保证数组按小于号从小到大有序！

• int n, a[1123456]; 前两个一般配合 -a 使用得到下标。
  • lower_bound(a + 1, a + n + 1, x) 返回第一个大于等于 x 的位置（指针/迭代器）
  • upper_bound(~) 返回第一个大于 x 的位置（指针/迭代器）
  • binary_search(~) 返回一个布尔值，表示能否查找到 x
  • 如果找不到，会返回最后一个位置的后一个位置。
• vector<int> a 前两个一般配合 -a.begin() 使用得到下标。
  • lower_bound(a.begin(), a.end(), x)
  • upper_bound(~)
  • binary_search(~)
  • 如果找不到，会返回 a.end()

注意：如果是从大到小有序的序列，查找第一个小于 x 的元素，那么需要指定第四个参数

小技巧：显然 upper_bound 减去 lower_bound 就是等于 x 的数量

set/map 上的查找

• set<int> s
  • s.lower_bound(x) 返回迭代器
  • s.upper_bound(x) 返回迭代器
  • s.find(x) 返回迭代器
  • s.count(x) 返回 0/1

上述方法会用容器底层实现的特性实现查找，如果直接用 lower_bound(a.begin(), a.end(), x) 会得到非最优的时间复杂度。

实数二分

#include <bits/stdc++.h>
using namespace std;
double f(double x)
{
    return 114 * x * x * x - 514 * x * x + 1919 * x - 810;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    double eps = 1e-12;
    double l = 0; // f(l) < 0
    double r = 1; // f(r) > 0
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (f(mid) < 0)
            l = mid;
        else
            r = mid;
    }
    cout << fixed << setprecision(10) << l << "\n";
    return 0;
}

二分答案

当可行解堆积在答案区间的某一侧，需要求解可行解与不可行解的交界点时，可以采用二分答案的方式处理。

一般来说都是一些：“正面求解答案”很困难，但是“验证某个答案是否合法”很简单，的题目中。

int l = ...;
int r = ...;
int ans = -1;
while (l <= r)
{
    int mid = (l + r) / 2;
    if (check(mid))
    {
        ans = mid;
        l = mid + 1;
    }
    else
        r = mid - 1;
}
cout << ans << "\n";

三分

const double eps = 1e-12;
double l = 0;
double r = 20;
while (r - l > eps)
{
    double L = (l + r) / 2;
    double R = (L + r) / 2;
    if (f(L) < f(R))
        r = R;
    else
        l = L;
}
cout << fixed << setprecision(10) << f(l);