c++ 二分查找代码 c++二分查找算法详解-C++-PHP中文网

c++ 二分查找代码 c++二分查找算法详解

尼克

发布： 2025-12-05 12:08:02

原创

778人浏览过

二分查找在有序数组中以O(log n)时间复杂度快速定位目标值，通过维护left和right指针，计算mid = left + (right - left) / 2避免溢出，比较arr[mid]与target决定搜索区间，迭代或递归实现，C++ STL提供binary_search、lower_bound、upper_bound等函数简化操作，使用时需确保数组有序并正确处理边界条件。

c++ 二分查找代码 c++二分查找算法详解

二分查找是一种在有序数组中快速查找目标值的高效算法，时间复杂度为 O(log n)。它通过不断缩小搜索范围，将问题规模每次减半，从而实现快速定位。C++ 中可以使用标准库函数，也可以手动实现。下面详细介绍其原理和代码实现。

二分查找基本原理

二分查找的前提是数组必须有序（升序或降序）。算法核心思想如下：

设定两个指针，left 指向数组起始位置，right 指向末尾位置。
计算中间位置 mid = left + (right - left) / 2，防止整数溢出。
比较 arr[mid] 与目标值 target：

若相等，返回 mid；
若 arr[mid]
若 arr[mid] > target，说明目标在左半部分，更新 right = mid - 1。

循环上述过程直到 left 超过 right，表示未找到，返回 -1。

手写二分查找代码（递归与迭代）

1. 迭代版本（推荐，效率高）

#include <iostream>
#include <vector>
using namespace std;
<p>int binarySearch(vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;</p><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) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
return -1; // 未找到

登录后复制

}

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

畅图

AI可视化工具

179

查看详情

// 示例调用 int main() { vector nums = {1, 3, 5, 7, 9, 11, 13}; int index = binarySearch(nums, 7); if (index != -1) cout

2. 递归版本

int binarySearchRecursive(vector<int>& arr, int target, int left, int right) {
    if (left > right) return -1;
<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, target, mid + 1, right);
else
    return binarySearchRecursive(arr, target, left, mid - 1);

登录后复制

}

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

// 调用方式：binarySearchRecursive(nums, 7, 0, nums.size()-1);

C++ 标准库中的二分查找

C++ STL 提供了多个用于二分查找的函数，定义在 gorithm> 头文件中：

std::binary_search：判断元素是否存在，返回 bool。
std::lower_bound：查找第一个大于等于 target 的位置，返回迭代器。
std::upper_bound：查找第一个大于 target 的位置。
std::equal_range：返回一对迭代器，表示所有等于 target 的元素范围。

示例：

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
<p>int main() {
vector<int> nums = {1, 3, 5, 7, 7, 7, 9, 11};</p><pre class='brush:php;toolbar:false;'>// 判断是否存在
bool found = binary_search(nums.begin(), nums.end(), 7);

// 查找第一个 >=7 的位置
auto it1 = lower_bound(nums.begin(), nums.end(), 7);
cout << "lower_bound at: " << (it1 - nums.begin()) << endl;

// 查找第一个 >7 的位置
auto it2 = upper_bound(nums.begin(), nums.end(), 7);
cout << "upper_bound at: " << (it2 - nums.begin()) << endl;

return 0;

登录后复制

}

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

使用 STL 函数能减少出错概率，尤其在处理边界情况时更安全。