二分法查找递归方式c语言
时间: 2023-04-03 19:02:54 浏览: 96
可以使用以下代码实现二分法查找的递归方式:
```
int binarySearch(int arr[], int left, int right, int target) {
if (left > right) {
return -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);
}
}
```
其中,arr为待查找的数组,left为数组左边界,right为数组右边界,target为要查找的目标值。如果找到目标值,则返回其下标;否则返回-1。
相关问题
c 语言二分法查找递归
下面是C语言实现二分法查找的递归版本代码:
```c
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
else
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void) {
int arr[] = {2, 5, 7, 9, 11, 13, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 11;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
printf("Element is not present in array");
else
printf("Element is present at index %d", result);
return 0;
}
```
在递归实现中,我们首先判断给定的数组区间是否有效(r >= l)。然后,我们计算中间元素索引mid,如果它与要查找的元素相等,我们返回mid。否则,如果中间元素大于要查找的元素,则我们将左半部分作为新的查找区间,并递归调用函数。否则,我们将右半部分作为新的查找区间,并递归调用函数。如果元素不存在,则返回-1。
c语言二分法查找特点
C语言二分法查找的特点如下:
```c
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
```
1. 二分法查找只适用于已排序的数组。
2. 二分法查找的时间复杂度为O(log n),比线性查找的O(n)更快。
3. 二分法查找的空间复杂度为O(1),只需要常量级的额外空间。
4. 二分法查找的实现通常使用迭代而不是递归,因为迭代的空间复杂度更低。
5. 二分法查找的实现需要注意边界条件,例如当数组为空或只有一个元素时应该特殊处理。