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

c++中如何使用递归实现二分查找_c++递归二分查找方法

下次还敢

发布： 2025-10-10 19:44:01

原创

219人浏览过

<p>递归实现二分查找通过不断缩小有序数组的搜索范围来定位目标值。首先判断左右边界是否有效，若无效则返回-1；计算中间索引mid，比较目标值与中间元素，相等则返回mid；若目标值较小，递归左半部分；若较大，递归右半部分。代码使用left + (right - left)/2防止溢出，确保更新边界正确避免死循环。适用于有序数组，逻辑清晰但栈空间消耗较大，大规模数据建议用循环替代。</p>

c++中如何使用递归实现二分查找_c++递归二分查找方法

在C++中，递归实现二分查找是一种经典且高效的算法方式。它通过不断缩小搜索范围，在有序数组中快速定位目标值。下面详细介绍如何用递归方法实现二分查找。

递归二分查找的基本思路

二分查找的前提是数组必须有序。递归的核心思想是：

确定当前查找区间的中间位置
将目标值与中间元素比较
如果相等，返回索引
如果目标值较小，递归查找左半部分
如果目标值较大，递归查找右半部分
如果区间无效（左边界大于右边界），说明未找到，返回-1

C++递归实现代码示例

#include <iostream>
using namespace std;
<p>// 递归二分查找函数
int binarySearch(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;
}

// 目标值在左半部分
if (target < arr[mid]) {
    return binarySearch(arr, left, mid - 1, target);
}

// 目标值在右半部分
return binarySearch(arr, mid + 1, right, target);

登录后复制

}

宣小二

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

查看详情

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

int main() { int arr[] = {1, 3, 5, 7, 9, 11, 13, 15}; int n = sizeof(arr) / sizeof(arr[0]); int target = 7;

int result = binarySearch(arr, 0, n - 1, target);

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

return 0;

登录后复制

}

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