在 C++ STL 的 <algorithm> 头文件中，lower_bound 和 upper_bound 是常用的二分查找函数，用于在有序容器中定位元素。本文将通过数组、vector、set 和 map 四种容器，详细说明它们的用法和区别。

数组中的使用

升序数组

• lower_bound(begin, end, num)：在 [begin, end) 范围内二分查找第一个 ≥ num 的元素，返回其指针；若未找到，返回 end。
• upper_bound(begin, end, num)：在 [begin, end) 范围内二分查找第一个 > num 的元素，返回其指针；若未找到，返回 end。

降序数组

• lower_bound(begin, end, num, greater<type>())：查找第一个 ≤ num 的元素。
• upper_bound(begin, end, num, greater<type>())：查找第一个 < num 的元素。

通过返回指针与起始地址的差值，可以获得元素下标。

#include <bits/stdc++.h>
using namespace std;
int arr[5] = {1, 4, 6, 6, 9};
int desc[5] = {9, 6, 3, 3, 1};

int main() {
    cout << lower_bound(arr, arr+5, 6) - arr << endl;   // 输出 2
    cout << upper_bound(arr, arr+5, 6) - arr << endl;   // 输出 4
    cout << lower_bound(desc, desc+5, 3, greater<int>()) - desc << endl; // 输出 2
    cout << upper_bound(desc, desc+5, 3, greater<int>()) - desc << endl; // 输出 4
    return 0;
}

vector 容器

vector 的用法与数组高度相似，调用方法几乎一致。

• lower_bound(vec.begin(), vec.end(), num)：升序查找第一个 ≥ num 的元素。
• upper_bound(vec.begin(), vec.end(), num)：升序查找第一个 > num 的元素。
• 降序时加上 greater<type>() 参数。

通过返回迭代器与 vec.begin() 的差值得到下标。

#include <bits/stdc++.h>
using namespace std;
vector<int> vec, dvec;

int main() {
    vec = {1, 4, 6, 6, 9};
    dvec = {9, 6, 3, 3, 1};
    cout << lower_bound(vec.begin(), vec.end(), 6) - vec.begin() << endl;   // 2
    cout << upper_bound(vec.begin(), vec.end(), 6) - vec.begin() << endl;   // 4
    cout << lower_bound(dvec.begin(), dvec.end(), 3, greater<int>()) - dvec.begin() << endl; // 2
    cout << upper_bound(dvec.begin(), dvec.end(), 3, greater<int>()) - dvec.begin() << endl; // 4
    return 0;
}

set 容器

set 的 lower_bound 是成员函数，语法与算法库中的不同。返回值是 set<type>::iterator 类型，指向第一个 ≥ num 的元素。由于 set 不是连续存储，不能通过迭代器减法获取下标。

#include <bits/stdc++.h>
using namespace std;
set<int> s;

int main() {
    s = {1, 4, 6, 6, 9};  // set 会自动去重，实际存储 {1,4,6,9}
    auto it = s.lower_bound(6);
    cout << *it << endl;  // 输出 6
    return 0;
}

map 容器

map 同样提供成员函数 lower_bound，返回 map<K,V>::iterator，指向第一个 key ≥ num 的键值对。同样不支持下标计算，但可以通过迭代器的 second 成员访问值。

#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;

int main() {
    mp[1] = 1; mp[2] = 4; mp[4] = 6; mp[5] = 6; mp[6] = 9;
    auto it = mp.lower_bound(3);  // 第一个 key ≥ 3 的元素是 (4,6)
    cout << it->second << endl; // 输出 6
    return 0;
}

总结要点

• 数组 / vector：使用 algorithm 中的函数，降序需指定 greater<type>() 参数。
• set / map：使用成员函数 lower_bound，无需 greater 参数（容器本身有序），返回迭代器而非指针。
• 所有容器均要求 有序 才能保证二分查找的正确性。
• 连续存储容器（数组、vector）可通过指针/迭代器差值获取下标；非连续容器（set、map）不可。