C++STL算法binary_search在有序序列应用

binary_search用于有序序列中高效查找元素，时间复杂度O(log n)，使用前需确保序列已排序，通常配合sort使用，支持自定义比较函数，适用于vector、array等随机访问容器，关联容器推荐用成员函数find。

在C++标准模板库（STL）中，binary_search 是一个非常实用的算法，用于判断某个值是否存在于已排序的序列中。它的时间复杂度为 O(log n)，比线性查找更高效，但前提是容器中的元素必须是有序的。

使用前提：序列必须有序

binary_search 只适用于有序序列。如果序列未排序，结果是未定义的，可能导致错误的判断。通常在使用前需调用 sort 算法进行排序。

• 使用 std::sort(vec.begin(), vec.end()) 对 vector 排序
• 之后才能安全使用 binary_search 查找元素

基本用法

binary_search 定义在头文件 <algorithm> 中，函数原型如下：

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

立即学习“C++免费学习笔记（深入）”；

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

0

查看详情

它返回一个布尔值：true 表示找到元素，false 表示未找到。

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

int main() {
    std::vector<int> nums = {5, 2, 8, 1, 9};
    std::sort(nums.begin(), nums.end()); // 排序

    if (std::binary_search(nums.begin(), nums.end(), 8)) {
        std::cout << "8 存在于序列中\n";
    } else {
        std::cout << "8 不存在\n";
    }
    return 0;
}

支持自定义比较函数

如果序列是按特定规则排序的（如降序），需要传入相应的比较函数或函数对象，确保 binary_search 使用相同的排序规则。

• 函数原型支持第四个参数：binary_search(first, last, value, comp)
• comp 应返回 true 当第一个参数小于第二个参数

std::vector<int> nums = {9, 8, 5, 2, 1};
// 无需重新排序，已是降序

bool found = std::binary_search(nums.begin(), nums.end(), 5, std::greater<int>());
if (found) {
    std::cout << "找到了 5\n";
}

适用容器类型

binary_search 可用于任何支持随机访问迭代器的有序容器，如：

• std::vector
• std::array
• std::deque
• 原生数组（配合指针）

注意：关联容器如 std::set 和 std::map 内部本身就是有序的，它们提供了成员函数 find 或 count，通常比使用 std::binary_search 更高效。

以上就是C++STL算法binary_search在有序序列应用的详细内容，更多请关注php中文网其它相关文章！