二分

理解：二分和二分查找并不是完全相同，虽然思路类似

Tips：

1. 二分区间的更新思路：Mid值保留还是丢弃？看Mid值的check是成功还是失败了，原则是：不能丢弃可能的正确值
2. 二分的结束条件：不好把握的话，可以把结束条件设定得宽松一点，比如：$r-l<3$的时候就结束，最后几个可能的值手动检查，虽然常数大了一点，但是更有把握

首先，使用二分查找的数据应该有序的

C++二分查找的STL函数

1. binary_search
2. lower_bound
3. upper_bound

参考资料：C++ STL中的Binary search（二分查找） https://www.cnblogs.com/wkfvawl/p/9475939.html

在 C++ 中，lower_bound 和 upper_bound 都是非常有用的标准库函数，用于在排序的序列中进行二分查找，以快速找到特定元素的位置。这两个函数都位于 <algorithm> 头文件中，并可以用于任何迭代器范围，如数组、向量、列表等。下面是这两个函数的详细解释和示例。

lower_bound

lower_bound 函数返回指向排序范围中第一个不小于（即大于或等于）给定值的元素的迭代器。如果所有元素都小于搜索的值，则返回指向范围末尾的迭代器。

语法

lower_bound(start, end, val);

• start 和 end 是定义要搜索的范围的迭代器。
• val 是要查找的值。

示例

#include <iostream>
#include <vector>
#include <algorithm>
 
int main() {
    std::vector<int> v = {1, 3, 3, 5, 7, 7, 9};
 
    // 查找第一个不小于 3 的元素
    auto it = lower_bound(v.begin(), v.end(), 3);
    std::cout << "The first element not less than 3 is at position: " << (it - v.begin()) << std::endl;
 
    return 0;
}

输出

The first element not less than 3 is at position: 1

upper_bound

upper_bound 函数返回指向排序范围中第一个大于给定值的元素的迭代器。如果所有元素都不大于搜索的值，则返回指向范围末尾的迭代器。

语法

upper_bound(start, end, val);

• start 和 end 是定义要搜索的范围的迭代器。
• val 是要查找的值。

示例

#include <iostream>
#include <vector>
#include <algorithm>
 
int main() {
    std::vector<int> v = {1, 3, 3, 5, 7, 7, 9};
 
    // 查找第一个大于 3 的元素
    auto it = upper_bound(v.begin(), v.end(), 3);
    std::cout << "The first element greater than 3 is at position: " << (it - v.begin()) << std::endl;
 
    return 0;
}

输出

The first element greater than 3 is at position: 3

使用场景

这两个函数常用于查找范围、计算特定元素在有序集合中的位置或数量（通过与 lower_bound 的差来计算），以及用于实现更复杂的数据结构和算法中的查找和排序操作。