有序数字序列{1, 2, 5, 7, 9, 10, 15, 20,28}, 写出用折半查找查找5的过程。

首先确定整个序列的中间位置，即索引为4的位置，此时中间元素为9。由于要查找的元素5小于中间元素9，因此在左半部分{1,2,5,7}中继续查找。再次确定左半部分的中间位置，即索引为1的位置，此时中间元素为2。由于要查找的元素5大于中间元素2，因此在右半部分{5,7}中继续查找。此时只剩下两个元素，确定中间位置，即索引为0的位置，此时中间元素为5，正是要查找的元素，返回其索引0即可。整个查找过程如下：

1. 确定中间位置，中间元素为9
{1, 2, 5, 7, 9, 10, 15, 20, 28}
↑
2. 由于要查找的元素5小于中间元素9，在左半部分继续查找
{1, 2, 5, 7}
↑
3. 确定左半部分的中间位置，中间元素为2
{1, 2, 5, 7}
↑
4. 由于要查找的元素5大于中间元素2，在右半部分继续查找
{5, 7}
↑
5. 只剩下两个元素，确定中间位置，中间元素为5，找到了要查找的元素
{5, 7}
↑

相关问题

设有有序数字序列a:{1, 2, 5, 7, 9, 10, 15, 20,28}, 写出用折半查找法查找15的过程

好的，我来为您演示一下用折半查找法查找15的过程：

1. 首先确定查找范围，因为序列是有序的，所以我们可以取最左边的元素下标left为0，最右边的元素下标right为8，即a序列的长度减1。

2. 计算中间位置mid，mid的计算公式为mid = (left + right) / 2，即mid = 4。

3. 比较a[mid]与要查找的元素15，因为a[mid] = 9 < 15，所以15应该在右半部分序列中。

4. 更新查找范围，因为15在右半部分序列中，所以我们可以把左边界left更新为mid+1，即left = 5。

5. 再次计算中间位置mid，mid的计算公式为mid = (left + right) / 2，即mid = 6。

6. 比较a[mid]与要查找的元素15，因为a[mid] = 15，所以查找成功，返回元素15的下标6。

因此，使用折半查找法可以在a序列中找到元素15，其下标为6。

写出折半查找（二分法查找）的递归算法。其中，有序表为ST，要查找的关键字为key，low表示当前查找序列的下界，high表示当前查找序列的上界。

好的，以下是折半查找的递归算法：

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。