c++中如何实现二分查找_c++ binary_search函数用法【实例】_技术教程

std::binary_search仅返回bool值表示存在性，不返回下标；需获取位置应使用std::lower_bound或std::upper_bound，且容器须升序排序、支持随机访问。

binary_search 函数本身不返回下标，只判存在性

std::binary_search 是 C++ 标准库提供的算法，定义在头文件中。它只返回 bool：找到返回 true，否则 false。它**不告诉你元素在哪儿**，所以不能直接替代“查找并返回位置”的需求。

常见误用是以为调用完 binary_search 就能拿到索引——实际不行。如果需要位置，得换用 std::lower_bound 或 std::upper_bound。

输入容器必须已升序排序（或按自定义比较器有序），否则行为未定义
时间复杂度是 O(log n)，但底层依赖随机访问迭代器，std::list 不能直接用
对 std::vector、std::array、原生数组指针可用；std::set 虽有序，但不支持随机访问，binary_search 无法用于其迭代器

正确用法：检查存在性 + 获取位置的组合写法

想既知道“有没有”，又知道“在哪儿”，推荐用 std::lower_bound —— 它返回第一个 ≥ 目标值的迭代器，再配合比较判断是否真等于目标值。

std::vector arr = {1, 3, 5, 7, 9, 11};
int target = 7;
auto it = std::lower_bound(arr.begin(), arr.end(), target);
if (it != arr.end() && *it == targe
t) {
size_t pos = std::distance(arr.begin(), it); // 得到下标
std::cout << "found at index " << pos << "\n";
} else {
std::cout << "not found\n";
}

std::lower_bound 和 binary_search 底层都是二分，性能一致
用 *it == target 判断“是否真存在”，比先调 binary_search 再调 lower_bound 更高效（避免两次二分）
若容器降序，需传入 std::greater{} 作为第 4 个参数，且所有相关操作（排序、查找）必须统一用同一比较器

自定义类型必须提供可比较逻辑

对结构体或类使用 binary_search 或 lower_bound，编译器需要能比较大小。要么重载 operator，要么显式传入比较函数对象。

struct Person {
    std::string name;
    int age;
};
bool operator<(const Person& a, const Person& b) {
    return a.age < b.age; // 按 age 排序和查找
}
std::vector people = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};
Person key = {"", 30};
bool found = std::binary_search(people.begin(), people.end(), key);

若没定义 operator，又没传比较器，编译失败，错误信息类似：invalid operands to binary expression ('const Person' and 'const Person')
比较逻辑必须和排序时完全一致，否则查找结果不可靠
建议把比较逻辑封装成 lambda 或命名函数，避免重复写错