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

c++中如何实现二分搜索_c++二分搜索实现方法

穿越時空

发布： 2025-10-14 21:23:01

原创

949人浏览过

二分搜索要求容器有序，通过比较中间值缩小范围，时间复杂度O(log n)。可用递归或迭代实现，推荐迭代以节省栈空间。C++ STL提供binary_search、lower_bound和upper_bound等函数，实际开发建议优先使用STL版本，更安全高效。

c++中如何实现二分搜索_c++二分搜索实现方法

在C++中实现二分搜索，前提是数组或容器必须是有序的。二分搜索通过不断缩小查找范围，将时间复杂度从线性搜索的O(n)降低到O(log n)。

基本思路

二分搜索的核心思想是：比较目标值与当前搜索区间的中间元素，根据比较结果决定向左或右继续搜索。

定义两个指针，left 和 right，表示当前搜索区间
计算中间位置：mid = left + (right - left) / 2（避免整数溢出）
如果中间值等于目标，返回索引
如果中间值小于目标，搜索右半部分
如果中间值大于目标，搜索左半部分
循环直到 left > right，未找到则返回-1

递归实现方式

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

登录后复制

}

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

查看详情

调用时传入初始区间：binarySearchRecursive(arr, 0, arr.size() - 1, target);

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

迭代实现方式（推荐）

int binarySearchIterative(const vector<int>& arr, int target) {
    int left = 0;
    int 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) left = mid + 1;
    else right = mid - 1;
}

return -1; // 未找到

登录后复制

}

迭代方式更节省栈空间，不易发生递归溢出，适合大规模数据。

使用STL中的二分搜索函数

C++标准库提供了几个高效的二分搜索函数，定义在 <algorithm> 头文件中：

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

示例：

vector<int> arr = {1, 3, 5, 7, 9};
bool found = binary_search(arr.begin(), arr.end(), 5); // true
auto it = lower_bound(arr.begin(), arr.end(), 6); // 指向7
int index = it - arr.begin(); // 索引为3

登录后复制

基本上就这些。手动实现有助于理解原理，实际开发中建议优先使用STL函数，更安全高效。

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