递归算法实现二分查找
时间: 2023-10-24 13:30:31 浏览: 72
递归算法实现二分查找是一种基于分治思想的算法。通过将数组不断地分成两半,然后在其中一半中查找目标值,再根据查找结果决定继续在左半部分还是右半部分进行查找,直到找到目标值或者确定目标值不存在为止。下面是一个使用C语言实现递归算法实现二分查找的示例代码:
```c
#include <stdio.h>
int binarySearch(int arr[], int min, int max, int key) {
if (min <= max) {
int mid = (min + max) / 2;
if (key == arr[mid]) {
return mid;
}
else if (key < arr[mid]) {
return binarySearch(arr, min, mid - 1, key);
}
else {
return binarySearch(arr, mid + 1, max, key);
}
}
return -1;
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 10, 13, 14, 17, 22, 33, 56, 78};
int len = sizeof(arr) / sizeof(int); int key = 33;
int result = binarySearch(arr, 0, len - 1, key);
if (result == -1) {
printf("目标值 %d 不存在于数组中\n", key);
}
else {
printf("目标值 %d 的下标是:%d\n", key, result);
}
return 0;
}
```
在这个示例代码中,我们定义了一个名为`binarySearch`的递归函数,它接受一个有序数组`arr`、最左边的边界`min`、最右边的边界`max`和目标值`key`作为参数。函数首先计算数组中间值的下标`mid`,然后与目标值进行比较。如果相等,则返回下标`mid`;如果目标值小于中间值,则继续在左半部分进行递归查找;如果目标值大于中间值,则继续在右半部分进行递归查找。如果最终无法找到目标值,则返回-1。在主函数中,我们定义了一个有序数组`arr`,设置了目标值`key`为33,并调用`binarySearch`函数进行查找。最后根据查找结果输出相应的信息。在这个示例代码中,递归函数实现了二分查找算法,通过不断地分割数组并在其中一半中查找,最终找到了目标值33,并返回了它的下标10。<span class="em">1</span><span class="em">2</span>
#### 引用[.reference_title]
- *1* [Python递归函数 二分查找算法实现解析](https://download.csdn.net/download/weixin_38716590/12860476)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* [C语言 递归函数实现二分查找](https://blog.csdn.net/weixin_44272350/article/details/119796743)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]