二分查找,二分答案
二分法
二分查找
- 确定在有序序列中,第一个满足某一条件的数的位置
二分答案:
- 求满足某一条件的最大/最小值时,对答案区间进行左右划分的算法。
题目特征: 求最小(大)值的最大(小)值
注意: 一定要小心边界,l,r分别为可能符合的最小/大值,而并非1和n
代码:
int l,r,mid,ans; l=1;r=n; //确定要查找的左右区间 while (l<=r){ //l>r时查找已经完成 mid=(l+r)/2; //先确定一个位置 if (......){ //判断是否满足条件 ans=mid; //如果满足,传出答案 [l=mid+1;] [r=mid-1;] //二选一 } else{ //否则重新确定范围 [r=mid-1;] [l=mid+1;] //二选一 } } cout<<ans<<endl;
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接:https://hs-blog.axell.top/archives/20/