1. 编写递归函数,实现二分查找问题。c
时间: 2024-10-11 07:15:05 浏览: 10
二分查找,也称为折半查找,是一种在有序数组中查找特定元素的搜索算法。递归实现的二分查找函数通常会分为两个步骤:
1. **基础条件**:检查给定数组是否为空或者长度为1,如果是,直接返回数组的索引位置(如果找到目标元素)或-1(未找到)。
2. **递归条件**:对于非空且长度大于1的数组,计算中间索引 `mid` 并比较目标值 `target` 与中间元素的值:
- 如果 `target` 等于中间元素,返回 `mid`。
- 如果 `target` 小于中间元素,说明目标应该在数组左半部分,所以在左半部分的范围 `[0, mid)` 再次调用函数,传入新的下限 `mid - 1`。
- 否则,如果 `target` 大于中间元素,说明目标在右半部分,所以在右半部分的范围 `(mid + 1, length)` 调用函数,传入新的上限 `mid + 1`。
这是一个简单的递归函数实现示例(在C语言中):
```c
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int target) {
if (left > right)
return -1; // 没有找到,返回 -1
int mid = left + (right - left) / 2;
// 目标等于中间元素
if (arr[mid] == target)
return mid;
// 目标小于中间元素,在左半部分递归查找
else if (arr[mid] > target)
return binarySearch(arr, left, mid - 1, target);
// 目标大于中间元素,在右半部分递归查找
else
return binarySearch(arr, mid + 1, right, target);
}
// 测试函数
int main() {
int arr[] = {1, 3, 5, 7, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found in the array\n");
return 0;
}
```