用递归的算法编写出对存入在 a[n+1]数组中的 n 个有序元素进行二分(又称折半)查找(假定 a[0]单元不用)的程序。
时间: 2023-12-20 08:03:42 浏览: 41
好的,以下是使用递归实现二分查找的程序:
```
int binarySearchRecursive(int a[], int left, int right, int x) {
if (left > right) {
return -1; // 表示未找到
}
int mid = left + (right - left) / 2;
if (a[mid] == x) {
return mid;
} else if (a[mid] < x) {
return binarySearchRecursive(a, mid + 1, right, x);
} else {
return binarySearchRecursive(a, left, mid - 1, x);
}
}
```
解释一下上面的代码:
- 接收四个参数:数组 a,左边界 left,右边界 right,目标元素 x。
- 如果左边界大于右边界,表示已经找完了整个待查找区间,但是还没有找到目标元素,返回 -1 表示未找到。
- 计算中间位置 mid,并用 a[mid] 与目标元素 x 进行比较。
- 如果相等,表示已经找到目标元素,返回 mid。
- 如果 a[mid] 小于 x,表示目标元素在右半边,递归调用自身,将左边界 left 调整为 mid + 1。
- 如果 a[mid] 大于 x,表示目标元素在左半边,递归调用自身,将右边界 right 调整为 mid - 1。
- 递归调用自身的过程会不断缩小待查找区间,直到找到目标元素或者整个待查找区间已经被缩小到只有一个元素为止。
这就是使用递归实现二分查找的基本思路,它的时间复杂度是 O(log n)。
相关推荐
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)