二分函数 lower_bound upper_bound

二分查找相关的函数主要定义在 <algorithm> 头文件中，用于在有序序列中快速查找元素，时间复杂度为 O(log n)。最常用的二分函数有以下三个：

1. lower_bound

• 功能：在有序序列中查找第一个大于等于目标值 val 的元素，返回其迭代器。
• 前提：升序。 

int main() {vector<int> v = {1, 3, 5, 7, 9};  // 升序排列int val = 5;// 查找第一个 >=5 的元素auto it = lower_bound(v.begin(), v.end(), val);if (it != v.end()) {cout << "找到元素位置：" << it - v.begin() << "，值：" << *it << endl;// 输出：找到元素位置：2，值：5}return 0;
}

2. upper_bound

• 功能：在有序序列中查找第一个大于目标值 val 的元素，返回其迭代器。
• 前提：升序。

3. equal_range

• 功能：在有序序列中查找与目标值 val 相等的所有元素的范围，返回一个 pair：
  • first：指向第一个大于等于 val 的元素（等同于 lower_bound 的结果）。
  • second：指向第一个大于 val 的元素（等同于 upper_bound 的结果）。
• 用途：快速获取所有等于 val 的元素（适合有重复元素的场景）。

4.自定义比较器

可通过第四个参数指定比较规则（如降序序列）： 

// 使用 greater<int>() 作为比较器（适配降序）
auto it = lower_bound(v.begin(), v.end(), 5, greater<int>());

不适用的容器

以下容器因不满足条件，不能使用二分函数：

1. 无序容器

• unordered_set / unordered_multiset：元素无序，不符合二分查找的前提。
• unordered_map / unordered_multimap：key 无序，无法使用二分函数。

2. 适配器容器

• stack、queue、priority_queue：不支持迭代器遍历（屏蔽了内部元素的直接访问），无法传递 begin() 和 end()。