二分答案

· · 算法·理论

二分答案

？这种东西为什么还要写blog啊看上去那么简单（

能水一篇blog 直接贴模板

int ll = 0, rr = ?, ans;
while(ll <= rr)
{
    int mid = (ll + rr) >> 1;
    if(half(mid))
    {
        rr = mid - 1;
        ans = mid;
    }
    else ll = mid + 1;
}

用于单调、连续的数列寻找答案，直接把复杂度O(n)变成O(logn)，多好啊（

一般来说主体由二分+验证答案是否可行两部分组成，但也能出很恶心的题