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

P1873

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

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

二分模板

while(l<=r){
	mid = (l+r)>>1;
	if(check(mid)){
		l = mid + 1;
	}else{
		r = mid - 1;
	}
}

搜索确定解的左右区间后，还要确定左右端点哪个才是题目需要的解。 例如本题，题目要求锯子的最高值 $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]$，然后对区间进行二分。

端点处理

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