二分与三分

二分的本质是在有序的答案空间中利用判定结果的单调性，每次排除一半区间；它不只用于在有序数组中找某个值。三分则用于单峰或单谷函数的最值搜索。

二分的适用条件与边界设计

先明确搜索范围、答案定义和 check(x) 的单调方向。例如 check 呈现 F...F T...T 时，可找第一个真值；呈现 T...T F...F 时，可找最后一个真值。二分前必须确认这种单调性，循环中必须保证区间严格缩小。

常见半开区间写法维护 [l, r)：令 r 取一个已知的“真”哨兵，循环结束时 l == r，即第一个真的位置。中点写成 l + (r - l) / 2，避免 l + r 溢出。

// 在 [L, R] 中找最小的 check(x) == true；不存在则返回 R + 1
long long firstTrue(long long L, long long R) {
    long long l = L, r = R + 1;
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

若寻找最后一个真值，可维护闭区间并使用上中位数 mid = l + (r - l + 1) / 2：真值时令 l = mid，否则令 r = mid - 1。上中位数保证 l + 1 == r 时仍能推进，避免死循环。

有序数组中的二分

lower_bound(begin, end, x) 返回第一个不小于 x 的位置，upper_bound 返回第一个大于 x 的位置。数组中 x 的出现次数为二者下标之差；查找后要判断迭代器未到 end 且元素确实等于 x。

int countValue(const vector<int>& a, int x) {
    auto first = lower_bound(a.begin(), a.end(), x);
    auto last = upper_bound(a.begin(), a.end(), x);
    return (int)(last - first);
}

单次二分时间为 O(log n)、额外空间为 O(1)。若数据未排序，不能直接按数值二分；应先排序（并注意下标语义）或选择其他方法。

答案二分

最优化问题常可转成“给定答案 x 是否可行”。例如最小化最大值时，阈值越大通常越容易可行；最大化最小值时，阈值越小通常越容易可行。完整步骤：确定答案的上下界；实现只返回可行/不可行的 check；证明其单调性；再选取“第一个可行”或“最后一个可行”的模板。

总时间为 O(log Range × T_check)，其中 Range 是答案范围，T_check 是一次判定的时间。计算容量、乘积或距离时应使用 long long，避免判定函数先溢出而破坏单调性。

实数二分与三分

实数二分同样要求判定函数单调，通常不依赖 l == r 结束，而是迭代固定次数（如 80～100 次）或直到区间长度小于精度 eps。输出时按题目要求控制精度。

三分适用于单峰函数（先增后减）求最大值，或单谷函数（先减后增）求最小值。每轮取 m1 = l + (r-l)/3、m2 = r - (r-l)/3，比较 f(m1) 与 f(m2) 后舍弃不可能含最优点的一段。连续函数可迭代到足够精度；离散整数区间通常循环缩小到较小范围后枚举剩余点，防止整除导致区间不缩小。

// 单峰实函数 f 的最大值位置
for (int it = 0; it < 100; ++it) {
    double m1 = l + (r - l) / 3.0;
    double m2 = r - (r - l) / 3.0;
    if (f(m1) < f(m2)) l = m1;
    else r = m2;
}
double answer = (l + r) / 2;

二分和三分都依赖可证明的单调或单峰性质；性质不成立时，缩小区间会错误地丢弃答案。