在折半查找递归的代码中加入注释
时间: 2024-05-30 09:13:01 浏览: 7
// 递归实现折半查找
int binarySearch(int arr[], int left, int right, int x) {
// 如果左边界大于右边界,说明数组中没有要查找的元素
if (left > right) {
return -1;
}
// 计算中间位置
int mid = (left + right) / 2;
// 如果中间位置等于要查找的元素,直接返回
if (arr[mid] == x) {
return mid;
}
// 如果中间位置大于要查找的元素,说明要查找的元素在左半部分
if (arr[mid] > x) {
// 递归查找左半部分
return binarySearch(arr, left, mid - 1, x);
}
// 如果中间位置小于要查找的元素,说明要查找的元素在右半部分
// 递归查找右半部分
return binarySearch(arr, mid + 1, right, x);
}
相关问题
折半查找递归c语言代码
折半查找(Binary Search)是一种常用的查找算法,它通过将查找区间逐渐缩小一半来快速定位目标元素。下面是使用递归方式实现的折半查找的C语言代码:
```c
#include <stdio.h>
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, 4, 6, 8, 10, 12, 14, 16};
int n = sizeof(arr) / sizeof(arr);
int target = 10;
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1) {
printf("目标元素未找到\n");
}
else {
printf("目标元素在数组中的索引为:%d\n", result);
}
return 0;
}
```
以上代码中,`binarySearch`函数使用递归方式实现了折半查找。它接受一个有序数组`arr`、查找区间的起始索引`low`和终止索引`high`,以及目标元素`target`作为参数。在每一次递归调用中,函数会计算中间元素的索引`mid`,并与目标元素进行比较。如果相等,则返回中间元素的索引;如果中间元素大于目标元素,则在左半部分继续查找;如果中间元素小于目标元素,则在右半部分继续查找。如果最终未找到目标元素,则返回-1。
c语言中实现折半查找递归算法并调用
好的,下面是 C 语言中实现折半查找递归算法的示例代码:
```c
#include <stdio.h>
int binarySearchRecursive(int arr[], int left, int right, int target) {
if (left > right) {
return -1;
}
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);
}
}
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int index = binarySearchRecursive(arr, 0, n - 1, target);
if (index != -1) {
printf("找到了,索引为 %d\n", index);
} else {
printf("没找到\n");
}
return 0;
}
```
以上代码实现了一个折半查找的递归算法,使用了递归的方式进行查找,时间复杂度为 O(log n)。在主函数中调用了 binarySearchRecursive 函数,并输出查找结果。注意要先定义好数组和目标值,然后传入函数中调用。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)