请用递归和非递归两种方式编写程序实现二分法查找。并给出时间复杂度T(n)和空间复杂度S(n)的结果。 设a=[1, 4, 8, 14, 25, 26, 37] C语言
时间: 2024-09-09 21:02:13 浏览: 35
递归方式实现二分查找的C语言代码示例如下:
```c
#include <stdio.h>
int binarySearchRecursive(int arr[], int left, int right, int x) {
if (right >= left) {
int mid = left + (right - left) / 2;
// 检查x是否在中间
if (arr[mid] == x)
return mid;
// 如果x大于中间值,则它只能在右子数组中
if (arr[mid] < x)
return binarySearchRecursive(arr, mid + 1, right, x);
// 否则,x只能在左子数组中
return binarySearchRecursive(arr, left, mid - 1, x);
}
// 如果元素不在数组中
return -1;
}
int main(void) {
int a[] = {1, 4, 8, 14, 25, 26, 37};
int n = sizeof(a) / sizeof(a[0]);
int x = 25; // 要查找的元素
int result = binarySearchRecursive(a, 0, n - 1, x);
if (result == -1)
printf("元素未找到");
else
printf("元素位于数组的索引 %d", result);
return 0;
}
```
非递归方式实现二分查找的C语言代码示例如下:
```c
#include <stdio.h>
int binarySearchIterative(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
// 检查x是否在中间
if (arr[m] == x)
return m;
// 如果x大于中间值,则它只能在右子数组中
if (arr[m] < x)
l = m + 1;
// 否则,x只能在左子数组中
else
r = m - 1;
}
// 如果元素不在数组中
return -1;
}
int main(void) {
int a[] = {1, 4, 8, 14, 25, 26, 37};
int n = sizeof(a) / sizeof(a[0]);
int x = 25; // 要查找的元素
int result = binarySearchIterative(a, 0, n - 1, x);
if (result == -1)
printf("元素未找到");
else
printf("元素位于数组的索引 %d", result);
return 0;
}
```
时间复杂度T(n)和空间复杂度S(n)如下:
- 时间复杂度:对于递归和非递归实现,二分查找的时间复杂度均为O(log n),因为每次操作都会将搜索区间减半。
- 空间复杂度:对于递归实现,空间复杂度为O(log n),这是因为在递归过程中会创建新的函数调用栈;对于非递归实现,空间复杂度为O(1),因为使用的是迭代而非递归,不涉及额外的函数调用栈空间。