对二分的最初讨论见 [[2023.12.22-2023.12.29#二分查找]]

P1873

二分的实质其实就是在一个解的可能范围内筛选出符合题意的解集，为了确保这个解可以被二分搜索到，题目一般具有以下特征：

1. 求最大/最小值;
2. 答案离散（答案有限）
3. 容易判断答案是否正确（check 函数）
4. 数据单调（注意是你搜的解相关变量单调，可能是题目输入经过一定处理后得到的单调序列）

二分模板

vector<int>::iterator find(vector<int> &num,int target){
    //对[0,n)范围进行二分查找
    int l = 0,r = num.size();
    while(l < r){
        int mid = (l + r) >> 1;//向下取整，靠近l，"左中位数"
        if(num[mid] >= target){
            r = mid;
        }else{
            l = mid + 1;//实数二分可以写l = mid，但是整数涉及取整问题，需要写成l = mid+1
            //当然这其实说不太准，重点是不死循环就行
        }
    }
    return (l<num.size() && l >= 0) ? num.begin() + l : num.end();
}

计算 mid 有多种方法，分别适用于以下情况： 显然一般情况选择第三种更好，仅需注意类型（或高精度）问题。 除此之外，还有寻找前驱的二分搜索模式，日后再讨论。 bin_search 只告诉这个元素是否存在，STL 的函数可以返回位置迭代器。

搜索确定解的左右区间后，还要确定左右端点哪个才是题目需要的解。 例如本题，题目要求锯子的最高值 $h$，所以对于搜索到的 $[l,r],r>l$，显然应该取最大值 $r$。

P1024

一道依托方程背景的二分，限制了解的范围在 $[-100，100]$，且每两个解之间的距离 $\ge 1$，根据零点存在定理：$f(x_1)\times f(x_2)\le 0$，可以先步长为 $1$ 地遍历 $[-100，100]$ 区间，找到异号区间 $[a,b]$，然后对区间进行二分。

端点处理

不加额外处理的二分查找不能处理端点的情况，一般可以通过增加[[树#哨兵]]来解决这些问题。 避免了搜索区间为空时候对边界上的特判，同时也可以减少循环条件的特判语句书写。