二分查找模板

• 算法思路:假设目标值在闭区间[l, r]中,每次将区间长度缩小一半，当l=r时,我们就找到了目标值。

模板一

• 找第一个满足或者第一个不满足check性质的元素

代码：

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1; 
        if (check(mid)) r = mid;    
        else l = mid + 1;
    }
    return l;
}

模板二

• 找最后一个满足或者最后一个不满足check性质的元素

代码：

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

二分的本质是二段性不是单调性：

• 具有单调性,可以二分。
• 没有单调性但具有某种区间性,也可二分。

复杂度分析：

• 时间复杂度：$O(\log{n})$
• 空间复杂度：$O(1)$