二分查找递归算法c++
时间: 2023-10-14 18:13:20 浏览: 71
以下是二分查找递归算法的C语言代码:
```
int binarySearch(int arr[], int low, int high, int key) {
if (high < low) {
return -1;
}
int mid = low + (high - low) / 2;
if (key == arr[mid]) {
return mid;
} else if (key < arr[mid]) {
return binarySearch(arr, low, mid - 1, key);
} else {
return binarySearch(arr, mid + 1, high, key);
}
}
```
其中,arr为已排序的数组,low和high分别为数组的起始位置和结束位置,key为要查找的元素。
首先判断high是否小于low,如果是,则返回-1,表示未找到。否则,计算中间位置mid,并将key与arr[mid]进行比较。如果相等,则返回mid,表示找到了该元素。如果key小于arr[mid],则递归查找前半部分数组,即low到mid-1位置的元素。否则,递归查找后半部分数组,即mid+1到high位置的元素。
相关问题
用C++写二分查找递归算法
当在一个有序数组中查找一个元素时,二分查找算法是一种高效的搜索方法。以下是使用C语言编写的递归算法示例:
```c
#include <stdio.h>
int binary_search_recursive(int arr[], int low, int high, int target) {
if (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binary_search_recursive(arr, mid + 1, high, target);
} else {
return binary_search_recursive(arr, low, mid - 1, target);
}
}
return -1;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int index = binary_search_recursive(arr, 0, n - 1, target);
if (index == -1) {
printf("Element not found in array");
} else {
printf("Element found at index %d", index);
}
return 0;
}
```
该递归算法将数组分为两半,并检查目标元素是否在左半部分、右半部分或中间位置。如果目标元素在左半部分,递归地调用函数并在左半部分进行二分查找;如果目标元素在右半部分,同样递归地调用函数并在右半部分进行二分查找;如果目标元素与中间元素匹配,函数将返回中间元素的索引。如果目标元素不在数组中,函数将返回-1。
递归算法实现二分查找c++
递归算法实现二分查找的C++代码如下:
```cpp
#include <iostream>
using namespace std;
int binarySearch(int arr[], int low, int high, int target) {
if (low <= high) {
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);
}
}
return -1; // 如果未找到目标元素,返回-1
}
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 << "目标元素未找到" << endl;
}
else {
cout << "目标元素位于索引 " << result << endl;
}
return 0;
}
```
以上代码使用递归实现了二分查找算法。在 `binarySearch` 函数中,首先判断数组的边界是否合法,如果不合法则返回 -1。然后计算中间元素的索引,与目标元素进行比较。如果中间元素等于目标元素,则返回中间索引;如果中间元素大于目标元素,则在左半部分继续查找;如果中间元素小于目标元素,则在右半部分继续查找。最后,如果未找到目标元素,则返回 -1。
在 `main` 函数中,我们定义了一个有序数组 `arr`,并指定目标元素为 23。然后调用 `binarySearch` 函数进行查找,并根据返回值输出查找结果。
运行以上代码,输出结果为:
```
目标元素位于索引 5
```
这表明目标元素 23 位于数组中的索引 5。