使用二分查找通过lower_bound和upper_bound计算有序数组中目标元素的出现次数，时间复杂度O(log n)，示例代码展示了标准库方法与手动实现边界查找的两种方式，适用于已排序数组的高效统计。
在C++中统计有序数组中某个元素的出现次数，可以利用数组的有序性来提升效率。最直接有效的方法是使用二分查找定位目标元素的左右边界，从而计算出其总出现次数。
使用标准库 lower_bound 和 upper_bound
对于已排序的数组，std::lower_bound 返回第一个不小于目标值的迭代器，而 std::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 出现了 3 次。这种方法时间复杂度为 O(log n)，适合大规模数据。
立即学习“C++免费学习笔记（深入）”；
手动实现二分查找获取边界
如果想更深入理解过程，也可以手动实现两个二分查找函数，分别找出目标元素的第一次和最后一次出现位置。
示例代码片段：
int findFirst(const std::vector<int>& arr, int target) {
int low = 0, high = arr.size() - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
high = mid - 1; // 继续向左找
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
<p>int findLast(const std::vector<int>& arr, int target) {
int low = 0, high = arr.size() - 1;
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
low = mid + 1; // 继续向右找
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}</p><p>int countOccurrencesManual(const std::vector<int>& arr, int target) {
int first = findFirst(arr, target);
int last = findLast(arr, target);
if (first == -1) return 0;
return last - first + 1;
}</p>这种方式逻辑清晰，便于调试和理解底层机制。
注意事项与适用场景
上述方法仅适用于已排序数组。若数组无序，需先排序再处理，但排序时间复杂度为 O(n log n)，可能不如直接遍历计数高效。
若只需统计单个元素频次，推荐使用 lower_bound 和 upper_bound；若需频繁查询多个不同元素的出现次数，可考虑预处理构建哈希表（前提是允许额外空间开销）。
基本上就这些。用好STL能大幅简化编码，同时保持高性能。
