C++ 第53题：基于有序序列的二分查找算法（std::binary_search 与 lower_bound/upper_bound）

题目

编写程序，在升序有序数组中系统应用 STL 二分查找三剑客：std::binary_search（仅返回是否存在布尔值）、std::lower_bound（返回第一个“大于等于 ≥ target”的迭代器）与 std::upper_bound（返回第一个“严格大于 > target”的迭代器）。演示如何利用后两者在 O(log N) 时间内精确计算某重复元素出现的频率区间。

输入格式：无需外部输入。

输出格式：输出目标元素的存在性、左闭右开区间范围与其在数组中出现的总次数。

数据范围与约定：有序序列二分查找边界开闭数学模型。

思路与算法

1. 二分前置硬性条件
三者全部要求输入区间必须已经升序排好序！若在无序数组上调用，将直接引发未定义行为，得出错误结果。

2. lower_bound 与 upper_bound 的区间本质
对于重复数字 target，lower_bound 给出的是首个等于 target 的位置；而 upper_bound 给出的是最后一个等于 target 的下一个位置。两者相减 std::distance(it1, it2) 恰好就是在 O(log N) 内统计重复频次的工业级解法！

3. 越界安全检查
返回的迭代器可能等于 vec.end()，在解引用 *it 之前必须先判断 it != vec.end()。

完整程序

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 升序数组，包含多个重复的 20
    std::vector<int> nums = {10, 20, 20, 20, 30, 40, 50};

    int target = 20;

    // 1. std::binary_search 纯布尔判定
    bool found = std::binary_search(nums.begin(), nums.end(), target);
    std::cout << "目标值 " << target << " 是否存在: " << std::boolalpha << found << "\n\n";

    // 2. lower_bound: 第一个 >= 20 的位置
    auto itLower = std::lower_bound(nums.begin(), nums.end(), target);
    // 3. upper_bound: 第一个 > 20 的位置
    auto itUpper = std::upper_bound(nums.begin(), nums.end(), target);

    int lowerIdx = std::distance(nums.begin(), itLower);
    int upperIdx = std::distance(nums.begin(), itUpper);

    std::cout << "lower_bound (首个 >= " << target << ") 下标: " << lowerIdx << "\n";
    std::cout << "upper_bound (首个 > " << target << ")  下标: " << upperIdx << "\n";

    // 4. 计算目标在有序数组中的重复出现频次
    int frequency = std::distance(itLower, itUpper);
    std::cout << "数字 " << target << " 出现频次 (upper - lower): " << frequency << " 次\n";

    return 0;
}

运行示例

输出：

目标值 20 是否存在: true

lower_bound (首个 >= 20) 下标: 1
upper_bound (首个 > 20)  下标: 4
数字 20 出现频次 (upper - lower): 3 次