用C语言将折半查找法改写为递归算法。
时间: 2024-02-22 07:58:53 浏览: 21
好的,折半查找法的递归实现如下:
```c
int binarySearchRecursive(int arr[], int low, int high, int target) {
if (low > high) {
return -1; // 找不到目标元素
}
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid; // 找到目标元素
} else if (arr[mid] > target) {
return binarySearchRecursive(arr, low, mid - 1, target); // 在左半部分继续查找
} else {
return binarySearchRecursive(arr, mid + 1, high, target); // 在右半部分继续查找
}
}
```
其中,`arr` 为要查找的数组,`low` 和 `high` 分别为数组的起始下标和结束下标,`target` 为要查找的目标元素。
在递归实现中,首先判断 `low` 是否大于 `high`,如果是,则说明查找失败,返回 `-1`。否则,计算中间位置 `mid`,如果 `arr[mid]` 等于 `target`,则说明找到了目标元素,返回 `mid`。如果 `arr[mid]` 大于 `target`,则在左半部分继续查找;否则,在右半部分继续查找。
相关问题
试将折半查找法改写为递归算法
好的,我来为您解答。折半查找法也叫二分查找法,是一种很常用的查找算法。下面是折半查找法的非递归实现:
```
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
```
现在我们将其改写为递归算法:
```
int binarySearchRecursion(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 binarySearchRecursion(arr, left, mid - 1, target);
else
return binarySearchRecursion(arr, mid + 1, right, target);
}
```
可以看到,递归算法的思想与非递归算法相同,只是将循环改成了递归函数调用,同时将循环条件改为递归终止条件。
试将折半查找法改写为递归算法。
好的,折半查找法的非递归实现如下:
```
int binarySearch(int arr[], int target, int length) {
int left = 0, right = length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
现在我们来将其改写为递归算法:
```
int binarySearchRecursion(int arr[], int target, int left, int right) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursion(arr, target, mid + 1, right);
} else {
return binarySearchRecursion(arr, target, left, mid - 1);
}
}
```
我们可以看到,在递归算法中,我们首先判断了递归的终止条件,即左指针大于右指针时,返回 -1。然后计算中间位置,如果中间位置的值等于目标值,直接返回 mid。否则,我们根据中间位置的值和目标值的大小关系分别递归查找左半部分和右半部分。