欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分算法总结

程序员文章站 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,同理,求最后一个的话,直接把数组从大到小倒着排列二分。