一、总结

\(STL\)里lower_bound和upper_bound都是找元素的插入位置，区别在于如果插入的值在数组中已经存在，这个插入位置有2种选择，可以插到第一个位置，也可以插到最后一个相同元素后面的位置，也就是插到头部还是尾部的区别。lower_bound是插到头部，upper_bound是\(append\)到后面。
如果数组里没有和插入值相同的元素，lower_bound和upper_bound的结果是一样的。

二、测试的例子

#include <bits/stdc++.h>

using namespace std;

int a[] = {1, 3, 5, 7, 9};

int main() {
    // 第一个大于等于1的元素是1，下标是0
    cout << (lower_bound(a, a + 5, 1) - a) << endl;

    // 第一个大于等于2的元素是3，下标是1
    cout << (lower_bound(a, a + 5, 2) - a) << endl;

    // 第一个大于等于8的元素是9，下标是4
    cout << (lower_bound(a, a + 5, 8) - a) << endl;

    // 最大的元素也不比100大，故返回值是last，再减a也就是5
    cout << (lower_bound(a, a + 5, 100) - a) << endl;

    cout << "==============================================" << endl;
    // 第一个大于1的元素是3，下标是1
    cout << (upper_bound(a, a + 5, 1) - a) << endl;

    // 第一个大于2的元素是3，下标是1
    cout << (upper_bound(a, a + 5, 2) - a) << endl;

    // 第一个大于7的元素是9，下标是4
    cout << (upper_bound(a, a + 5, 7) - a) << endl;

    // 最大的元素也不比100大，故返回值是last，再减a也就是5
    cout << (upper_bound(a, a + 5, 100) - a) << endl;

    return 0;
}

三、问题及思考

如果要求第一个小于\(x\)的数，或者第一个小于等于\(x\)的数怎么办呢？

还是用上面两个函数就可以了

查找第一个小于等于\(x\)的数（注：这里的意思为小于\(x\)的数里最大的那个）
算法：upper_bound()的返回值 - \(1\)，就是要查找的地址

比如数组是\(int a[] = {1, 3, 5, 7, 9}\)要查找的数\(x\)是\(3\)
用upper_bound()找到的是第一个大于\(3\)的数对吧，它的返回值是\(5\)的地址，把返回结果再减\(1\)就好了，就是\(3\)的地址了。第一个小于等于\(3\)的元素是\(3\)，没错吧！

这是刚好数组里有\(x\)的情况，那如果没有呢？比如要查找的元素是\(4\)，那upper_bound()的返回值是\(5\)的地址，再减\(1\)，就是\(3\)的地址了，第一个小于等于\(4\)的元素是\(3\)，没错吧！

那如果查的元素比第一个元素还要小呢，比如\(-1\)，那\(upper_bound()\)的返回值是\(a\)，再减\(1\)就是\(a\)的前一个单元了。所以这里得特判了，要不然出错误了。

查找第一个小于\(x\)的数
算法：lower_bound()的返回值 - \(1\)，就是要查找的地址
还是用上面的数据为例子
要查找的元素为\(7\)，lower_bound的返回值为\(7\)的地址，再减\(1\)就是\(5\)的地址，第一个小于\(7\)的元素是\(5\)，没错。
要查找\(8\)呢，lower_bound()返回的是\(9\)的地址，再减\(1\)就是\(7\)，没错。
查找\(-1\)，lower_bound()返回\(1\)的地址，也就是\(a\)，再减\(1\)为\(a\)的前一个单元，会越界，需要特判。