C++ lower_bound和upper_bound

学习笔记 C++STL

https://www.zybuluo.com/scrolllock/note/1279274

在一个有序容器的前闭后开的区间中,二分查找某个某个数$X$的上下界位置
$lower\_bound$查找第一个$\geq X$的位置
$upper\_bound$查找第一个$>X$的位置
如图

对于数组的测试代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[] = {1, 2, 2, 3, 4, 4, 5, 5, 5, 6, 7};
    for (int i = 0; i <= 10; i ++) printf("a[%d] = %d\n", i, a[i]);
    printf("\n");
    int pos;
    pos = lower_bound(a, a + 10 + 1, 5) - a;
    printf("lower_bound(a    , a + 10 + 1, 5) - a : %d\n", pos);
    pos = lower_bound(a + 1, a + 10 + 1, 5) - a;
    printf("lower_bound(a + 1, a + 10 + 1, 5) - a : %d\n", pos);
    pos = lower_bound(a + 1, a + 10 + 1, 5) - a;
    printf("lower_bound(a + 1, a + 10 + 1, 0) - a : %d\n", pos);
    pos = upper_bound(a + 1, a + 10, 5) - a;
    printf("upper_bound(a + 1, a + 10 + 1, 5) - a : %d\n", pos);
    pos = upper_bound(a + 1, a + 10, 8) - a;
    printf("upper_bound(a + 1, a + 10 + 1, 8) - a : %d\n", pos);
    return 0;
}

输出:

a[0] = 1
a[1] = 2
a[2] = 2
a[3] = 3
a[4] = 4
a[5] = 4
a[6] = 5
a[7] = 5
a[8] = 5
a[9] = 6
a[10] = 7
lower_bound(a    , a + 10 + 1, 5) - a : 6
lower_bound(a + 1, a + 10 + 1, 5) - a : 6
lower_bound(a + 1, a + 10 + 1, 0) - a : 6
upper_bound(a + 1, a + 10 + 1, 5) - a : 9
upper_bound(a + 1, a + 10 + 1, 8) - a : 10