值得下载！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
二分查找是一种高效的搜索算法，尤其适用于已排序的数组或链表。在C++中，二分查找可以手工实现，也可以使用STL（标准模板库）中的`lower_bound`和`upper_bound`这两个系统函数来完成。下面我们将深入探讨这些知识点。
手工实现二分查找通常涉及三个主要变量：`Left`、`Right`和`Mid`。初始时，`Left`和`Right`分别代表数组的起始和结束下标。在循环中，我们不断计算中间值`Mid`，并根据目标值`x`与`a[Mid]`的比较结果来调整搜索范围。当`Left > Right`时，表示未找到目标值，返回-1。以下是两种常见的二分查找实现方式：
1. 查找目标值`x`首次出现的下标：
```cpp
int BinarySearch(int L, int R, int x) {
while (L <= R) {
int Mid = (L + R) / 2;
if (x == a[Mid]) return Mid;
if (x > a[Mid]) L = Mid + 1;
else R = Mid - 1;
}
return -1;
}
```
2. 查找目标值`x`等于或大于的最小下标：
```cpp
int BinarySearch(int L, int R, int x) {
while (L < R) {
int M = (L + R) / 2;
if (a[M] < x) L = M + 1;
else R = M;
}
return L;
}
```
3. 查找目标值`x`大于或等于的最小下标：
```cpp
int BinarySearch(int L, int R, int x) {
while (L < R) {
int M = (L + R + 1) / 2;
if (a[M] <= x) L = M;
else R = M - 1;
}
return L;
}
```
接下来，C++ STL提供了`lower_bound`和`upper_bound`两个系统函数，它们也使用了二分查找的思想。`lower_bound`返回大于等于`Value`的第一个元素的迭代器，而`upper_bound`返回大于`Value`的第一个元素的迭代器。这两个函数的原型如下：
```cpp
iterator lower_bound(iterator Begin, iterator End, const T& Value);
iterator upper_bound(iterator Begin, iterator End, const T& Value);
```
它们的参数包括：
- `Begin` 和 `End`：分别表示序列的起始和结束迭代器。
- `Value`：要查找的值。
返回值是一个迭代器，指向满足条件的元素。如果没有找到满足条件的元素，返回`End`。
例如，对于数组`A`，`lower_bound(A, A+13, 7)`会返回数组中第一个大于等于7的元素的迭代器，`upper_bound(A, A+13, 7)`则返回第一个大于7的元素的迭代器。
在某些场景下，可能需要自定义比较函数。为此，可以向`lower_bound`和`upper_bound`提供第四个参数，它是一个比较函数对象或比较函数指针。
对于题目“人数统计”，我们可以使用`lower_bound`和`upper_bound`来快速统计数组中特定值`k`的出现次数。首先对数组进行排序，然后用`upper_bound`减去`lower_bound`的结果即可得到数量：
```cpp
sort(A, A + n);
cnt = upper_bound(A, A + n, k) - lower_bound(A, A + n, k);
```
这个方法在处理大规模数据时非常高效，尤其是在数据范围`n ≤ 100000`，询问次数`m ≤ 80000`的情况下。
总结来说，二分查找是编程中常用的一种算法，C++的STL提供了便捷的`lower_bound`和`upper_bound`函数来支持这一操作，使得在有序序列中查找特定元素或范围变得简单而高效。在解决实际问题时，理解并熟练运用这些工具能够大大提高代码质量和效率。
