二分查找

在一段单调的序列上查找一个数，可以采用折半的方法，每次将查找的范围缩小一半

模板：

l=1,r=n;
while(l<=r){
    int mid=(l+r)/2;
		if(x<=a[mid]) r=mid-1;
	else l=mid+1;
}
cout<<l<<endl;

查找的复杂度为$ \mathcal{O}(\text{log}n)$

STL函数：

lower_bound(first,last,val);//first,last及返回值都为迭代器,可在最后加比较器

在非递减区间 $[first,last)$ 中进行二分查找，返回大于或等于 $val$ 的第一个元素位置。如果所有元素都小于 $val$ ，则返回 $last$ 的位置。

upper_bound(first,last,val);//first,last及返回值都为迭代器,可在最后加比较器

在非递减区间 $[first,last)$ 中进行二分查找，返回大于 $val$ 的第一个元素位置。如果所有元素都小于$val$ ，则返回 $last$ 的位置。

二分答案

适用条件：

  1. 最优解满足单调性
  2. 最优解满足有界性

即：

对于 $[a,b]$ 区间内的最优解 $x_0,$ 满足：

$\forall x_1<x_0 , x_1$ 均为次优解，$\forall x_2>x_0,x_2 $ 均为不可行解。

模板：

while(l<=r){ 
	mid=(l+r)/2; 
	if(sol(mid)) r=mid-1; 
	else l=mid+1; 
} 
cout<<l<<endl;

大部分二分答案的题目的框架是不变的，变化的只有两个部分：

  1. $sol$ 函数：根据每个题目写出具体的判断函数，需要注意取等条件

  2. 最终答案：需要具体判断

    当 $l==r$ 的时候，判断最终答案是 $l$ 还是 $l-1$

一般来说，二分答案的题目的解很难直接求出，但很容易判断一个解是否可行

例题

P3017 [USACO11MAR]Brownie Slicing G

看到题目中的最大值最小，考虑用二分验证

前缀和维护即可