C++怎么实现一个二分查找算法_C++算法入门与有序数组查找-C++-PHP中文网

C++怎么实现一个二分查找算法_C++算法入门与有序数组查找

冰火之心

发布： 2025-11-28 09:19:53

原创

675人浏览过

二分查找适用于有序数组，通过比较中间值缩小范围，时间复杂度O(log n)。可手动实现循环或递归版本，也可使用C++ STL的binary_search、lower_bound等函数。注意数组有序、防溢出计算mid、正确设置边界和循环条件。

c++怎么实现一个二分查找算法_c++算法入门与有序数组查找

二分查找是一种高效的查找算法，适用于已排序的数组。它通过不断缩小查找范围，将时间复杂度从线性查找的 O(n) 降低到 O(log n)。在 C++ 中实现二分查找，既可以使用手动编写循环或递归的方式，也可以借助标准库函数。

基本原理与实现思路

二分查找的核心思想是：在有序数组中，取中间元素与目标值比较：

如果中间元素等于目标值，返回其下标。
如果中间元素大于目标值，说明目标在左半部分。
如果中间元素小于目标值，说明目标在右半部分。

重复这个过程，直到找到目标或搜索区间为空。

手动实现二分查找（循环版本）

#include <iostream>
#include <vector>
using namespace std;
<p>int binarySearch(const 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++免费学习笔记（深入）”；

uBrand Logo生成器

uBrand Logo生成器是一款强大的AI智能LOGO设计工具。

124

查看详情

int main() { vector<int> nums = {1, 3, 5, 7, 9, 11, 13}; int target = 7; int result = binarySearch(nums, target);

if (result != -1) {
    cout << "元素 " << target << " 在索引 " << result << " 处找到。\n";
} else {
    cout << "元素 " << target << " 未找到。\n";
}

return 0;

登录后复制

}

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

使用 C++ 标准库函数

C++ STL 提供了多个与二分查找相关的算法，定义在 <algorithm> 头文件中：

binary_search(first, last, val)：判断 val 是否存在于 [first, last) 区间。
lower_bound(first, last, val)：返回第一个不小于 val 的元素位置。
upper_bound(first, last, val)：返回第一个大于 val 的元素位置。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
<p>int main() {
vector<int> nums = {1, 3, 5, 7, 9, 11, 13};
int target = 7;</p><pre class='brush:php;toolbar:false;'>if (binary_search(nums.begin(), nums.end(), target)) {
    cout << "元素存在。\n";
}

auto it = lower_bound(nums.begin(), nums.end(), target);
if (it != nums.end() && *it == target) {
    cout << "元素在索引 " << (it - nums.begin()) << " 处。\n";
}

return 0;

登录后复制

}

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