写出折半查找(二分法查找)的递归算法。其中,有序表为ST,要查找的关键字为key,low表示当前查找序列的下界,high表示当前查找序列的上界。
时间: 2024-02-09 22:10:31 浏览: 27
好的,以下是折半查找的递归算法:
```
int BinarySearch(int ST[], int key, int low, int high) {
if (low > high) { // 如果下界大于上界,说明没找到
return -1;
}
int mid = (low + high) / 2; // 计算中间位置
if (key == ST[mid]) { // 如果中间位置正好是关键字,直接返回
return mid;
} else if (key < ST[mid]) { // 如果关键字小于中间位置的值,说明在左半边
return BinarySearch(ST, key, low, mid - 1);
} else { // 如果关键字大于中间位置的值,说明在右半边
return BinarySearch(ST, key, mid + 1, high);
}
}
```
函数返回值为查找到的关键字在有序表中的下标,如果没找到则返回-1。
相关问题
用C语言写出有序表折半查找的递归算法
下面是用C语言实现有序表折半查找的递归算法:
```c
int BinarySearch(int A[], int low, int high, int key) {
if (low <= high) {
int mid = (low + high) / 2;
if (A[mid] == key) {
return mid;
} else if (A[mid] > key) {
return BinarySearch(A, low, mid - 1, key);
} else {
return BinarySearch(A, mid + 1, high, key);
}
}
return -1;
}
```
其中,`A`为有序表,`low`和`high`分别为表的最小索引和最大索引,`key`为要查找的关键字。首先判断`low`是否小于等于`high`,如果是,则计算中间位置`mid`,如果`A[mid]`等于`key`,则返回`mid`;如果`A[mid]`大于`key`,则在`low`到`mid-1`之间继续查找;如果`A[mid]`小于`key`,则在`mid+1`到`high`之间继续查找。如果`low`大于`high`,则表示表中不存在关键字,返回-1。
写出有序表折半查找的递归算法代码c
下面是有序表折半查找的递归算法代码C语言实现:
```c
int binarySearch(int arr[], int left, int right, int target) {
if (left > right) {
return -1; // 如果左边界大于右边界,说明查找失败
}
int mid = (left + right) / 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); // 如果中间位置的值小于目标值,说明目标值在右半部分
}
}
```
这段代码中,我们通过递归的方式实现了有序表折半查找。首先,我们判断左边界是否大于右边界,如果是的话,说明查找失败,返回-1。然后,我们计算中间位置,如果中间位置的值等于目标值,说明查找成功,返回中间位置。如果中间位置的值大于目标值,说明目标值在左半部分,我们对左半部分递归调用该函数。如果中间位置的值小于目标值,说明目标值在右半部分,我们对右半部分递归调用该函数。