【算法】二分学习笔记

二分查找

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

模板：

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

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

前缀和维护即可