c++中如何实现二分查找_c++二分查找实现方法-C++-PHP中文网

c++中如何实现二分查找_c++二分查找实现方法

穿越時空

发布： 2025-10-02 18:59:01

原创

311人浏览过

二分查找要求数据有序，通过递归或迭代实现O(log n)高效搜索，C++ STL提供binary_search、lower_bound等函数推荐优先使用。

c++中如何实现二分查找_c++二分查找实现方法

在C++中实现二分查找，核心前提是数组或容器中的元素必须是有序排列的。二分查找通过不断缩小搜索范围，将时间复杂度从线性查找的 O(n) 降低到 O(log n)，非常适合处理大规模有序数据。

基本二分查找（递归实现）

递归方式直观地体现二分思想：每次比较中间元素，根据大小决定向左或右继续查找。

#include <iostream>
#include <vector>
<p>int binarySearchRecursive(const std::vector<int>& arr, int left, int right, int target) {
if (left > right) return -1; // 未找到</p><pre class='brush:php;toolbar:false;'>int mid = left + (right - left) / 2; // 防止整数溢出

if (arr[mid] == target) return mid;
else if (arr[mid] > target)
    return binarySearchRecursive(arr, left, mid - 1, target);
else
    return binarySearchRecursive(arr, mid + 1, right, target);

登录后复制

}

非递归（迭代）实现

迭代方式更节省空间，避免递归调用栈开销，实际开发中更常用。

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

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

int binarySearchIterative(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
<pre class='brush:php;toolbar:false;'>while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] == target) return mid;
    else if (arr[mid] > target) right = mid - 1;
    else left = mid + 1;
}
return -1; // 未找到

登录后复制

}

使用STL中的二分查找函数

C++标准库提供了现成的二分查找工具，简洁且高效，推荐优先使用。

std::binary_search：只判断元素是否存在，返回 bool 值
std::lower_bound：返回第一个不小于 target 的位置
std::upper_bound：返回第一个大于 target 的位置

#include <algorithm>
<p>bool found = std::binary_search(arr.begin(), arr.end(), target);</p><p>auto it = std::lower_bound(arr.begin(), arr.end(), target);
if (it != arr.end() && *it == target) {
int index = it - arr.begin(); // 获取下标
}</p>

登录后复制

基本上就这些。手动实现有助于理解原理，但在实际项目中建议直接使用 STL 函数，减少出错概率，提升开发效率。注意确保数据有序，否则结果不可靠。

以上就是c++++中如何实现二分查找_c++二分查找实现方法的详细内容，更多请关注php中文网其它相关文章！