前言:

坚持每天更新博客，今天复习二分查找

概述:

二分查找相较于普通的查找的时间复杂度更小，为O（logn）。

二分查找主要针对一段单调的区间，然后将区间分为左右两个部分，通过判断不断缩小范围直到找到答案。

模板

其实模板1和模板2本质上是根据代码来区分的，而不是应用场景。如果写完之后发现是l = mid，那么在计算mid时需要加上1，否则如果写完之后发现是r = mid，那么在计算mid时不能加1。

版本一:

1
2
3
4
5
6
7
8
9
10
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;
}

版本二

1
2
3
4
5
6
7
8
9
10
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;
}