c++折半查找递归算法完整代码
时间: 2024-12-10 12:15:19 浏览: 71
折半查找也叫二分查找,是一种在有序数组中查找特定元素的搜索算法。以下是C++中使用递归实现的折半查找算法的完整代码:
```cpp
#include <iostream>
using namespace std;
// 递归函数用于执行折半查找
int binarySearch(int arr[], int low, int high, int target) {
// 基本情况:数组为空或只有一个元素
if (low > high)
return -1; // 如果目标值不在数组中,返回 -1
// 计算中间索引
int mid = low + (high - low) / 2;
// 检查中间元素是否为目标值
if (arr[mid] == target)
return mid; // 找到目标,返回其索引
// 否则,如果目标小于中间元素,则在左半部分递归查找
else if (arr[mid] > target)
return binarySearch(arr, low, mid - 1, target);
// 否则,在右半部分递归查找
else
return binarySearch(arr, mid + 1, high, target);
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1)
cout << "Element found at index " << result << endl;
else
cout << "Element not found in the array" << endl;
return 0;
}
```
在这个代码中,`binarySearch` 函数接收一个排序好的整数数组 `arr`、起始索引 `low`、结束索引 `high` 和要查找的目标值 `target`。它会不断将搜索范围减半,直到找到目标元素或者范围为空。若未找到,最后返回 -1。
阅读全文