使用二分查找通过lower_bound和upper_bound确定左右边界，其差值即为目标元素出现次数，时间复杂度O(log n)，代码简洁高效。
在C++中统计有序数组中某个元素的出现次数，可以利用数组的有序特性，使用二分查找来高效定位目标元素的左右边界，从而计算出其出现次数。这种方法时间复杂度为 O(log n)，远优于暴力遍历的 O(n)。
1. 使用 lower_bound 和 upper_bound
C++标准库提供了 std::lower_bound 和 std::upper_bound，非常适合处理有序数组：
- lower_bound 返回第一个不小于目标值的迭代器
- upper_bound 返回第一个大于目标值的迭代器
- 两者之差即为目标元素的出现次数
示例代码：
#include <vector>
#include <algorithm>
#include <iostream>
<p>int countOccurrences(const std::vector<int>& arr, int target) {
auto left = std::lower_bound(arr.begin(), arr.end(), target);
auto right = std::upper_bound(arr.begin(), arr.end(), target);
return right - left;
}</p><p>int main() {
std::vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
int target = 2;
std::cout << target << " 出现了 " << countOccurrences(arr, target) << " 次\n";
return 0;
}</p>2. 手动实现二分查找
如果不使用STL函数，也可以手动实现二分查找来找到左右边界：
立即学习“C++免费学习笔记（深入）”；
查找左边界：
int findLeftBound(const std::vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
查找右边界：
int findRightBound(const std::vector<int>& arr, int target) {
int left = 0, right = arr.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
统计次数：
int count = findRightBound(arr, target) - findLeftBound(arr, target);
3. 处理不存在的元素
如果目标元素不在数组中，lower_bound 和 upper_bound 返回相同位置，差值为0，因此无需额外判断，结果自然为0。手动实现时也具备同样特性。
基本上就这些方法。利用有序性加二分查找是这类问题的标准解法，既简洁又高效。
