C++学习随笔——C++STL中binary_search的使用方法

std::binary_search 是 C++ 标准模板库 (STL) 中的一个算法，用于在有序范围内查找某个值是否存在。它基于二分查找算法，时间复杂度为 O(log n)。

std::binary_search 的基本用法：

  bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

• first: 指向范围的起始迭代器。
• last: 指向范围的结束迭代器。
• value: 要查找的值。

示例代码：

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

int main() {
    // 创建并排序一个整数向量
    std::vector<int> vec = {1, 3, 5, 7, 9, 11};
    
    // 查找一个存在的元素
    int value_to_find = 5;
    bool found = std::binary_search(vec.begin(), vec.end(), value_to_find);
    
    if (found) {
        std::cout << value_to_find << " found in the vector." << std::endl;
    } else {
        std::cout << value_to_find << " not found in the vector." << std::endl;
    }
    
    // 查找一个不存在的元素
    value_to_find = 6;
    found = std::binary_search(vec.begin(), vec.end(), value_to_find);
    
    if (found) {
        std::cout << value_to_find << " found in the vector." << std::endl;
    } else {
        std::cout << value_to_find << " not found in the vector." << std::endl;
    }

    return 0;
}

带有比较函数的 std::binary_search：

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

示例代码：

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

struct Person {
    std::string name;
    int age;

    // 定义小于操作符以按年龄排序
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };
    
    // 对 people 按年龄排序
    std::sort(people.begin(), people.end());

    Person target = {"", 25}; // 只关心年龄，不关心名字

    // 使用自定义比较函数进行二分查找
    bool found = std::binary_search(people.begin(), people.end(), target, [](const Person& p1, const Person& p2) {
        return p1.age < p2.age;
    });
    
    if (found) {
        std::cout << "Person with age " << target.age << " found in the vector." << std::endl;
    } else {
        std::cout << "Person with age " << target.age << " not found in the vector." << std::endl;
    }

    return 0;
}

注意事项

• 有序性要求：std::binary_search 假定输入范围已经按照升序排序。如果数据没有排序，可能会得到错误的结果或无效的返回值。
• 查找多个相等的元素：如果范围中有多个与 value 相等的元素，std::binary_search 只会返回 true 或 false，而不会告诉你元素的具体位置或数量。

std::binary_search 非常适合用于快速检测一个有序序列中是否存在某个元素。如果需要找到元素的具体位置，可以使用 std::lower_bound 或 std::upper_bound。