二分
①二分概念:
二分算法，又称折半查找，即在一个单调有序的集合中查找一个解。每次分为左右两部分，判断解在哪个部分中并调整上下界，直到找到目标元素，每次二分后都将舍弃一半的查找空间。
②时间复杂度: $O(logn)$
③二分常见模型:
- 二分查找:在一个单调有序的区间上求解分界点。
- 二分答案:最小值最大(最大值最小)问题，这类双最值问题常常选用二分法进行求解，也就是确定答案后，配合贪心、DP等其他算法检验这个答案是否合理，将最优化问题转换为判定性问题。
注：一般题目默认在一个从小到大的区间上。
一、整数二分
1. 查找精确值
从一个有序数组中找到一个符合要求的精确值(如猜数游戏)。如查找值为$key$的元素下标,不存在返回$-1$。
区间划分为：$[l,mid-1],mid,[mid+1,r]$。
int binary_search(int l,int r,int key)
{
/*
l<=r的原因:
如果最后只剩下a[pos]和a[pos+1]这两个元素,此时l=pos,r=pos+1
计算出mid=(l+r)/2=(pos+pos+1)/2=pos
当a[mid]<key,此时l=mid+1=pos+1,继续检测第pos+1个元素;
反之写成l<r时,此时会直接退出循环,不再检测第pos+1个元素,导致答案错误
*/
while(l<=r)
{
int mid=(l+r)/2;
if(a[mid]==key)
return mid;
//[l,mid-1]-----mid-----[mid+1,r]
//由于mid在上个if中不成立时(即mid不是最终答案),此时可把mid排除在外
else if(a[mid]>key)
r=mid-1;
else l=mid+1;
}
return -1;
}
2. 查找大于等于/大于key的第一个元素
这种通常题目描述为满足某种情况的最小的元素。
区间划分为：$[l,mid],[mid+1,r]$
int binary_search(int l,int r,int key)
{
while(l<r)
{
/*
此处不需要+1,即不写成mid=(l+r+1)/2;
如果最后只剩下a[pos]和a[pos+1]这两个元素,此时l=pos,r=pos+1
计算出mid=(l+r)/2=(pos+pos+1)/2=pos
如果a[mid]>key,那么之后l=r=pos,跳出循环
如果a[mid]<key,那么之后l=r=pos+1,跳出循环,故不会造成死循环
*/
int mid=(l+r)/2;
if(a[mid]>key)
//如果求大于等于则写成a[mid]>=key,此处也可以是check(mid)
//if(check(mid))
r=mid;
else l=mid+1;
//如果a[mid]<key,那么a[mid]以及小于a[mid]的值都需排除在外,故l=mid+1
}
return l;
}
举例:
设原数组个数为$7$,元素序列为$[1,3,5,8,10,12,15]$,用该二分查找代码查找$11$
- 第一次:$l=1,r=7,mid=(l+r)/2=4$,此时$a[mid]=8<11$,更新$l=mid+1=5$;
- 第二次:$l=5,r=7,mid=(l+r)/2=6$,此时$a[mid]=12>11$,更新$r=mid=6$;
- 第三次:$l=5,r=6,mid=(l+r)/2=5$,此时$a[mid]=10<11$,更新$l=mid+1=6$,此时$l=r=6$退出循环.
最终得到结果为$12$(下标为$6$)。$12$是查到数组中大于$11$(查找数)的最小值。
故该二分代码用来解决最大值最小化问题。
3. 查找小于等于/小于key的最后一个元素
这种通常题目描述为满足某种情况的最大的元素。
区间划分为：$[l,mid-1],[mid,r]$
int binary_search(int l,int r,int key)
{
while(l<r)
{
/*
这里mid=(l+r+1)/2;
如果最后只剩下a[pos]和a[pos+1]这两个元素,此时l=pos,r=pos+1
计算出mid=(l+r+1)/2=(pos+pos+1+1)/2=pos+1
如果a[mid]<key,l=r=pos+1,跳出循环;如果a[mid]>key,l=pos+1-1=pos,跳出循环
*/
int mid=(l+r+1)/2;
//如果求小于等于则写成a[mid]<=key,此处也可以是check(mid)
if(a[mid]<key)
//如果A[mid]<key,说明比A[mid]更小的数肯定不是小于key的最大的元素
//所以要排除mid之前的所有元素
l=mid;
else r=mid-1;
//如果A[mid]>key，那么说明A[mid]以及比A[mid]还要大的数都不可能小于key
//所以排除A[mid]及其之后的元素。
}
return l;
}
举例:
设原数组个数为$7$,元素序列为$[1,3,5,8,10,12,15]$,用该二分查找代码查找$11$
- 第一次:$l=1,r=7,mid=(l+r+1)/2=4$,此时$a[mid]=8<11$,更新$l=mid=4$;
- 第二次:$l=4,r=7,mid=(l+r+1)/2=6$,此时$a[mid]=12>11$,更新$r=mid-1=5$;
- 第三次:$l=4,r=5,mid=(l+r+1)/2=5$,此时$a[mid]=10<11$,更新$l=mid=5$,此时$l=r=5$退出循环.
最终得到结果为$10$(下标为$5$)。$10$是查到数组中小于$11$(查找数)的最大值。
故该二分代码用来解决最小值最大化问题。
4. 总结
最后两种情况的循环跳出条件是$l < r$，为什么不是小于等于呢？因为我们的区间变换思路是不断的舍去不可能是解的区间，最后只剩下一个数就是我们的解。而第一种情况就算最后只剩一个数也有可能不是解，所以需要使用小于等于。
- 查找精确值，循环条件是小于等于；查找满足情况的最大最小值，循环条件是小于。
- 查找满足条件的最大数，$mid=(l+r+1)/2$；查找满足条件的最小数，$mid=(l+r)/2$
- 如果存在没有解的情况，比如从$[1,2,3,4,5]$找出大于等于$6$的第一个数，我们只需要将最后剩下的数单独进行一次判断。
二、浮点二分
类似于数学对函数实行的二分法。
const double eps=1e-6;//精度具体题目具体分析
double binary_search(double l,double r)
{
while(l+eps<r)
{
double mid=(l+r)/2;
if(check(mid))
r=mid;
else l=mid;
}
return l;
}
三、STL二分函数
1. 以有序数组为例
在从小到大的数组中,查找区间$[l,r)$某种情况的元素$k$;
查找范围:$[l,r)$。时间复杂度为:$O(logn)$。
lower_bound(a+l,a+r,k) //二分查找第一个大于或等于k的数字
upper_bound(a+l,a+r,k) //二分查找第一个大于k的数字
对于$lower$_$bound$来说，当元素$k$存在时返回指向该元素的地址，如果$k$大于数组中任何一个值，则返回指向$r$的地址。如果$k$小于数组中任何一个值，则返回指向$l$的地址。同理，$upper$_$bound$类似。
- 技巧：因为返回的是数组地址，所以可以减去数组来求得在数组中的位置。
int t=lower_bound(a+l,a+r,k)-a;
- 此时,若$t$属于$[l,r)$,则$a[t]\geqslant k$。
2. 重载二分函数
重载为在从大到小的数组中，查找区间$[l,r)$某种情况的元素$k$，或者在一个结构体数组中实行二分查找。
lower_bound(a+l,a+r,k,greater<int>() )
//二分查找第一个小于或等于k的数字
lower_bound(a+l,a+r,k,cmp)
//cmp 相当于重载 <
- 当元素$k$存在时返回指向该元素的地址，如果$k$大于数组中任何一个值，则返回指向$l$的地址。如果$k$小于数组中任何一个值，则返回指向$r$的地址。
3. 二分函数运用于其他容器中
除$vector$可变长数组，$deque$双端队列，$set$集合，$multiset$外，其他容器很少用二分函数或者不能用二分函数。
lower_bound(a.begin()+l,a.begin()+r,k) - a.begin();
//vector 可变长数组，deque 双端队列，其实和数组差不多
set<int>::iterator it = a.lower_bound(k) ;
//set ，集合，只能查找全体，返回的是迭代器,multiset和set差不多
4. 与find()比较
- $find()$一般是$O(n)$的时间复杂度，但序列可以是无序的。
- $lower$_$bound()$一般是$O(logn)$的时间复杂度，但序列必须的有序的。
- 二者各有优劣，当数据量较大时尽量使用$lower$_$bound()$。
四、二分答案
- 二分答案一般求解最小值最大（最大值最小）问题，将求解答案二分，配合贪心、DP等其他算法检验这个答案是否合理，将最优化问题转换为判定性问题。
- 一般整数问题整数二分，实数问题浮点数二分，本质是一样的。
- 复杂度一般为$O(nlogn)$，适合解决再$10^5$范围内的数据。
