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