二分查找可以根据查找区间的不同分类，常见的类型有左闭右闭型与左闭右开型。

下面以左闭右闭型为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
std::vector<int> a(n + 1);

int bs(int key)
{
    int l = 1, r = n;
    while(l <= r)
    {
        int mid = ((r - l) >> 1) + l;
        if(a[mid] > key)
        {
            r = mid - 1;
        }
        else if(a[mid] < key)
        {
            l = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

对于不同类型的二分查找，其实现细节略有不同（比如对左闭右开型的二分，其终止条件换为l < r，并且右区间的更改也变为r = mid（注意左区间的更改不变）。详见B站UP主“代码随想录”的视频BV1fA4y1o715）

C++还提供了定义在头文件algorithm中的函数upper_bound()和lower_bound()用于二分查找。

下面提供一个例子，实现与C++函数lower_bound()类似的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
std::vector<int> a(n + 1);

int lbs(int key)
{
    int ans = -1;
    int l = 1, r = n;
    while(l <= r)
    {
        int mid = ((r - l) >> 1) + l;
        if(a[mid] >= key)
        {
            ans = mid;
            r = mid -1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}