C++如何用二分查找法在有序数组中找数-C++-PHP中文网

std::lower_bound最快最安全，返回首个≥目标的迭代器，未找到时等于end()，避免手写二分的越界风险与性能损耗。

c++如何用二分查找法在有序数组中找数

用 `std::lower_bound` 最快也最安全

直接调标准库，比手写二分快、无越界风险、还支持自定义比较。它返回第一个 ≥ 目标值的迭代器，没找到就等于 end()：

int arr[] = {1, 3, 5, 7, 9};
int n = 5;
int target = 5;
auto it = std::lower_bound(arr, arr + n, target);
if (it != arr + n && *it == target) {
    std::cout <p>注意：必须确保数组升序，否则行为未定义；<code>std::lower_bound</code> 是左闭右开区间语义（<code>[first, last)</code>），别传错长度。</p><h3>手写二分时边界条件怎么设才不漏不越界</h3><p>核心是统一用 <code>[left, right]</code> 闭区间，while 条件用 <code>left ，更新时 <code>right = mid - 1</code> 和 <code>left = mid + 1</code> —— 这样所有整数位置都能被覆盖，且不会死循环：</code></p>

别用 [left, right) 却忘了改 while 条件为 left
别在 arr[mid] == target 后直接 return，除非你确定只要一个位置；想找第一个/最后一个，得继续收缩边界
mid 计算用 left + (right - left) / 2，防止 left + right 溢出（尤其指针差值大时）

找第一个/最后一个位置不能只靠 `==` 判断

重复元素存在时，普通二分可能停在中间任意一个位置。要找最左，就在 arr[mid] == target 时继续往左搜：right = mid - 1；找最右则往右搜：left = mid + 1。最后检查边界是否合法：

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

// 找第一个位置
int left = 0, right = n - 1, ans = -1;
while (left <p>返回 <code>ans</code> 前务必确认它不是 -1，且 <code>arr[ans] == target</code> —— 有些实现会把 <code>ans</code> 初始化成 <code>left</code> 或 <code>right</code>，容易误判。</p><h3>用 <code>std::binary_search</code> 只判断存不存在</h3><p>如果只需要布尔结果（有/没有），用它最轻量。它不返回位置，内部也是调 <code>lower_bound</code>，但少一次解引用：</p><pre class="brush:php;toolbar:false;">bool exists = std::binary_search(arr, arr + n, target);

别指望它返回索引；也不要对降序数组用它——它默认按 比较，降序得传 <code>std::greater<int>()</int>。

边界检查和数组有序性是所有方法共通的前提，漏掉这个，再对的逻辑也会崩。