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 == target) {
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 或命名函数，避免重复写错

手写二分查找要注意边界和死循环

标准库函数可靠，但面试或特殊场景（比如找插入点、找左/右边界）常需手写。最容易出错的是 while 条件和 mid 更新方式。

• 闭区间写法（left ）更直观，但更新时必须 left = mid + 1 和 right = mid - 1，否则卡死
• 左开右闭（left ）适合找插入位置，right 初始化为 n，更新用 right = mid
• 计算 mid 推荐写成 left + (right - left) / 2，防止 left + right 溢出（尤其 int 大数组）
• 查不到时返回什么？-1？n？还是 std::optional？需根据业务明确约定

边界细节多，标准库已覆盖绝大多数情况，优先用 lower_bound；手写只在需要精细控制（如多次调用、定制比较逻辑、或教学目的）时才值得投入精力。