递归算法和非递归算法实现二分查找c语言
时间: 2024-09-09 20:14:45 浏览: 34
递归算法和非递归算法都是用于在有序数组中实现二分查找的有效方法。
**递归算法实现二分查找(C语言)**:
```c
int binarySearchRecursive(int arr[], int low, int high, int target) {
if (low > high)
return -1; // 如果目标不在数组内,返回-1
int mid = low + (high - low) / 2; // 计算中间索引
if (arr[mid] == target)
return mid; // 找到目标,返回其索引
else if (arr[mid] < target)
return binarySearchRecursive(arr, mid + 1, high, target); // 目标大于中间元素,搜索右半部分
else
return binarySearchRecursive(arr, low, mid - 1, target); // 目标小于中间元素,搜索左半部分
}
```
**非递归算法实现二分查找(C语言)**:
```c
int binarySearchIterative(int arr[], int target, int n) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1; // 没有找到目标,返回-1
}
```
**相关问题--:**
1. 递归和非递归二分查找的主要区别是什么?
2. 递归版本的空间复杂度如何?
3. 为什么在处理大数据量时更倾向于选择非递归算法?