整数二分
Terrible
·
·
个人记录
这里只是讨论了一种模板样式，其他样式等待更新。
下文里的 check(mid) 是一个 bool 函数，是反映枚举出的 mid 是否符合要求的函数，也可以理解为一个判断语句。
整数二分的两个关键点
（i）mid 是向下取整 mid=(l+r)/2 还是向上取整 mid=(l+r+1)/2：
考虑区间 [l,r] 长度只有 2 的时候（l+1==r 时） mid 的计算方法会不会造成死循环。
（ii）l 和 r 的赋值情况：
首先明确 [l,r] 所框定的范围对应的概念，例如：
$[l,r]$ 框定了第一个 `check(i)==0` 的位置 `i`；
$[l,r]$ 框定了最后一个 `check(i)==1` 的位置 `i`；
$[l,r]$ 框定了最后一个 `check(i)==0` 的位置 `i`；
注：$[l,r]$ 表示 $l\leqslant i\leqslant r$ 的 `i` 的集合；其中的 `check(i)` 函数满足单调性，或者说，至多只有一处分界点 `i0` 使得 `check(i0)!=check(i0+1)`
如果 $[l,r]$ 范围内全是 $1$，那么不可以查出来 $0$ 的位置；如果 $[l,r]$ 的范围内全是 $0$，那么不可以查出来 $1$ 的位置。如果查不出来对应的位置，结果一般而言不正确。
相对应地，根据设定的概念，来决定相应的取值。
### 以第一种情况为例
假设 `check(mid)` 是 `1`，那么意味着第一个 `check(i)==1` 对应的点 `i` $\leqslant$ `mid`，那么更新后的区间为 $[l,mid]$，赋值 `r=mid`即可；
同样 `check(mid)` 是 `0`，那么意味着连同 `mid` 和比它小的下标中都没有 `check(i)==1` 的情况，更新范围为 $[mid+1,r]$ ，赋值 `l=mid+1` 即可。
此种情况应当选用 `mid=(l+r)/2` 向下取整的方式，因为如果区间长度为 2 时（`l+1==r` 时），若 `mid` 始终取到的值是 `r`，此时 `check(r)==1`，那么赋值 `r=mid`（emmm，似乎没有变化），就会死循环。
可能地，`mid` 上下取整可以看 `l` 和 `r` 赋值的时候出现的是 `mid-1` 还是 `mid+1`（`mid-1` 对应上取整，`mid+1`对应下取整）。
```cpp
#include<cstdio>
int a[11]={0,1,1,2,3,4,5,6,6,7,8},x=6;
bool check(int mid)
{
return a[mid]>=x;
};//check(i):{0,0,0,0,0,0,0,1,1,1,1};
int main()
{
int l=1,r=10;//第一个满足 a[i]>=x 的 i 包含在 [l,r] 中
while(l<r)//l==r 跳出循环，因为此时 [l,r] 是一个点，就是解了
{
int mid=(l+r)/2;//向下取整
if(check(mid))r=mid;//[l,mid]
else l=mid+1;//[mid+1,r]
}
//最后答案是 l，a[l]>=x，且 a[l-1]<x
printf("%d",l);//l==7
return 0;
}
```