上机练习6.3.7 用递归算法实现二分查找,即:有n个已经从小到大排序好的数据(不重复),从键盘输入一个数X,用对半查找方法,判断它是否在这n个数中。用C实现 输入 第一行,正整数n,N<=105; 第二行,n个整数(int范围内,不重复),中间用空格分隔; 第三行,整数X。 输出 如果找到X,输出其位置;否则输出-1。 样例输入 Copy 10 10 20 30 40 50 60 70 80 90 100 90 样例输出 Copy 9
时间: 2025-06-27 15:06:22 浏览: 13
下面是基于题目要求的一个完整 C 实现,并结合了递归二分查找算法:
```c
#include <stdio.h>
// 定义递归函数原型
int binarySearch(int arr[], int left, int right, int x);
int main() {
int n;
scanf("%d", &n); // 输入数组大小
int arr[n];
for (int i = 0; i < n; i++) { // 输入已排序的数组元素
scanf("%d", &arr[i]);
}
int x;
scanf("%d", &x); // 输入目标值 X
// 调用二分查找函数,范围初始化为 [0, n-1]
int result = binarySearch(arr, 0, n - 1, x);
if (result != -1) {
printf("%d\n", result + 1); // 输出索引位置(转换为人习惯的位置计数)
} else {
printf("-1\n"); // 找不到时输出 -1
}
return 0;
}
// 递归实现二分查找
int binarySearch(int arr[], int left, int right, int x) {
if (left > right) { // 基本条件:找不到时返回 -1
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == x) { // 如果找到,则直接返回该位置
return mid;
} else if (arr[mid] > x) { // 目标在左半部分
return binarySearch(arr, left, mid - 1, x);
} else { // 目标在右半部分
return binarySearch(arr, mid + 1, right, x);
}
}
```
### 程序解析:
1. **主程序流程**:
- 首先读取 `n` 和包含 `n` 个数字的有序数组;
- 接着读入需要查找的目标数值 `X`;
- 使用递归函数 `binarySearch()` 对整个数组进行搜索。
2. **关键点说明**:
- 初始边界设置为 `[0, n-1]`, 即全数组范围内的初始状态。
- 每次迭代通过计算中位数 `mid` 并比较当前值与目标值的关系缩小搜索空间。
- 若等于则立即返回结果;
- 否则继续递归搜索左边或右边的部分直到无法再划分为止。
3. **复杂度分析**:
- 时间复杂度 O(log N),因为每次都将问题规模减小一半。
- 空间复杂度取决于栈深度,最坏情况下的递归层数也是 O(log N).
---
阅读全文
相关推荐
















