二分算法总结
程序员文章站
2022-05-22 15:17:45
...
求某序列中第一个(最后一个满足条件的值)的模板
while(left<right) //必须是小于,小于的话当左右相等,夹出来的就是答案,加上等于的话,最后left就不是答案(最后的else)多此一举。
{
int mid=(left+right)/2;
if(check(mid))
{
right=mid;
}
else
{
left=mid+1;
}
}
cout<<left;
这里注意,左右分别是0和n(数组下标从0开始),为什么不是n-1是因为如果没有满足条件的就返回n,同理,求最后一个的话,直接把数组从大到小倒着排列二分。