C++如何实现二分查找-C++-PHP中文网

绝大多数情况下应使用std::binary_search等标准库函数而非手写二分，仅教学、无stl环境或需极致内存控制时才手写；lower_bound找首个≥target位置，upper_bound找首个>target位置。

c++如何实现二分查找

什么时候该自己写 `std::binary_search` 而不是手撸循环

绝大多数情况下，你不需要手动实现二分查找——std::binary_search、std::lower_bound、std::upper_bound 已经覆盖所有常见需求。手写容易出边界错误，且编译器对标准库的优化更充分。

只有两种情况值得自己写：

教学/面试明确要求手写逻辑
目标平台无 STL（如某些嵌入式环境），或需极致控制内存访问模式（如 cache 友好型二分）

`std::lower_bound` 和 `std::upper_bound` 的关键区别在哪

它们都返回迭代器，但语义不同：std::lower_bound 找第一个 ≥ target 的位置；std::upper_bound 找第一个 > target 的位置。两者结合能精准定位重复元素区间。

示例：

vector<int> v = {1, 2, 2, 2, 3, 4};
auto lo = lower_bound(v.begin(), v.end(), 2); // 指向第1个2（索引1）
auto up = upper_bound(v.begin(), v.end(), 2); // 指向3（索引4）
int count = distance(lo, up); // 得到3，即2出现次数
</int>

注意：两个函数都要求容器已升序排列，否则行为未定义。

手写二分时最容易错的三个边界条件

用 while (left 还是 <code>while (left ？中点怎么算？左右指针怎么更新？这些细节直接决定是否漏掉元素或死循环。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

推荐统一用闭区间写法（left ），并始终用 <code>mid = left + (right - left) / 2 避免溢出：

查存在性：找到 arr[mid] == target 就返回 true；否则按大小关系缩区间
查下界（first ≥ target）：arr[mid] 时 <code>left = mid + 1；否则 right = mid - 1，最后返回 left
查上界（first > target）：arr[mid] 时 <code>left = mid + 1；否则 right = mid - 1，最后返回 left

别用 (left + right) / 2，整数溢出在大数组里真会发生。

自定义比较逻辑时，`std::lower_bound` 的第三个参数必须匹配

如果你传了自定义比较函数（比如按结构体某个字段排序），那调用 std::lower_bound 时第三个参数不能只是值，而得是能被该比较函数接受的类型。

例如：

struct Node { int key; string val; };
vector<node> v = {{1,"a"}, {3,"b"}, {5,"c"}};
auto it = lower_bound(v.begin(), v.end(), 3,
                      [](const Node& a, int k) { return a.key <p>如果顺序写反（比如 <code>[](int k, const Node& a)</code>），编译会失败；如果只传 <code>3</code> 却没提供 comparator，它会尝试用 <code>Node ，大概率报错。</code></p>
<p>实际项目里，这类错误往往卡在编译阶段，但调试时容易忽略 lambda 的参数顺序约定。</p></node>