C语言中如何高效实现二分查找算法，核心技巧是什么？

本文共计875个文字，预计阅读时间需要4分钟。

由于边界条件、溢出、迭代器失效等问题，以下代码示例可能无法正常工作：

• 它要求容器已排序（升序），且支持随机访问迭代器（vector、array 可用，list 不行）
• 返回第一个 ≥ 目标值的迭代器，没找到就返回 end()，不用自己判空
• 内部用的是半开区间 [first, last)，和绝大多数 STL 算法一致，不会因闭区间习惯出错
• 整数下标场景下，别直接用 int 算中点：mid = (left + right) / 2 可能溢出；std::lower_bound 内部用 std::distance 安全处理

手写二分时 mid 计算必须用 left + (right - left) / 2

不是为了“看起来高级”，是防止 left 和 right 都接近 INT_MAX 时加法溢出 —— 这种溢出不报错，但结果变成负数，后续下标访问直接 UB（未定义行为）。

• 错误写法：mid = (left + right) / 2
• 正确写法：mid = left + (right - left) / 2
• 如果用 size_t 或其他无符号类型，还得多一层检查：right >= left，否则 right - left 会回绕成极大正数
• C++20 起可用 std::midpoint(left, right)，它自动处理有/无符号、溢出、指针等所有情况

查找失败时返回什么值最容易引发逻辑 bug

很多人默认返回 -1，但在无符号类型（如 size_t）上下文中，-1 会变成极大正数（如 18446744073709551615），后续用作索引或比较时悄无声息地出错。

• 统一用有符号整型（如 int）做返回值，或直接返回迭代器（推荐）
• 若必须返回下标，检查调用方是否可能将返回值赋给 size_t：比如 auto idx = binary_search(...); vector.at(idx); —— 这里 idx 是 -1 就崩了
• 更稳妥的做法是返回 std::optional<size_t></size_t>（C++17+），调用方必须显式判断是否有值

std::binary_search 只告诉你“在不在”，但你往往需要位置

std::binary_search 返回 bool，适合纯存在性判断；但多数真实场景要的是下标、插入点或范围（比如找所有等于某值的元素）。

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

• 要下标：用 std::lower_bound，然后减去 begin() 得到索引
• 要插入位置（保持有序）：std::lower_bound 的返回迭代器就是该插的位置
• 要找一段相等值：配合 std::upper_bound，[lower_bound, upper_bound) 就是完整区间
• 注意：三个函数都要求严格升序；如果容器是降序，得传 std::greater() 作为比较器，否则行为未定义

边界条件、迭代器有效性、类型符号性 —— 这些地方不写注释、不加断言、不测极端输入，上线后出问题根本看不出哪来的。