下列算法的功能为：采用折半方法进行关键字的查找,请将算法中缺失的语句按照顺序填入对应的空格。 结构定义： typedef int KeyType; typedef struct{ KeyType key; }ElemType; typedef struct { ElemType *elem; int length; } SSTable; 折半查找算法： int Search_Bin(SSTable &ST,KeyType key){ //在有序表ST中折半查找其关键字等于key的数据元素 //若找到，则函数值为该元素在表中的位置，否则为0 int low=1, high=ST.length,mid; while(low<=high){ ; // (1) if(EQ(key, )) // (2) return mid; else if(LT(key,ST.elem[mid].key)) ; // (3) else ; // (4) } return 0; }

折半查找算法：

int Search_Bin(SSTable &ST,KeyType key){
//在有序表ST中折半查找其关键字等于key的数据元素
//若找到，则函数值为该元素在表中的位置，否则为0
int low=1, high=ST.length,mid;
while(low<=high){
mid = (low+high)/2; // (1) 折半计算中间位置
if(EQ(key, ST.elem[mid].key)) // (2) 关键字与中间位置元素相等
return mid;
else if(LT(key,ST.elem[mid].key)) // (3) 关键字小于中间位置元素
high = mid-1;
else // (4) 关键字大于中间位置元素
low = mid+1;
}
return 0;
}

相关问题

从键盘输入一整数，然后在一个整型一维数组 a[20]中，用折半查找法找出该数是数 组中第几个元素的值。如果该数不在数组中，则打印”no found”。

### 回答1：
首先，我们需要先读取从键盘输入的整数，可以使用 scanf 函数实现：

int num;
scanf("%d", &num);

然后，我们需要定义一个整型一维数组 a[20]，并对其进行初始化。这里我们假设数组已经初始化完成。

接下来，我们可以使用折半查找法来查找该数在数组中的位置。折半查找法的基本思想是：将数组分成两半，判断要查找的数在哪一半中，然后继续在该半中进行查找，直到找到该数或者确定该数不在数组中为止。

具体实现如下：

int low = , high = 19, mid;
while (low <= high) {
    mid = (low + high) / 2;
    if (a[mid] == num) {
        printf("该数在数组中的位置是：%d\n", mid + 1);
        break;
    } else if (a[mid] < num) {
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}
if (low > high) {
    printf("no found\n");
}

在上面的代码中，我们首先定义了三个变量：low、high 和 mid，分别表示数组的最小下标、最大下标和中间下标。然后，我们使用 while 循环进行查找，直到找到该数或者确定该数不在数组中为止。

在每次循环中，我们首先计算出中间下标 mid，然后判断要查找的数 num 是否等于 a[mid]。如果相等，说明找到了该数，输出该数在数组中的位置，并使用 break 语句跳出循环。

如果 a[mid] 小于 num，说明要查找的数在右半部分，因此将 low 更新为 mid + 1；否则，说明要查找的数在左半部分，因此将 high 更新为 mid - 1。

最后，如果 low 大于 high，说明该数不在数组中，输出“no found”。

完整代码如下：

#include <stdio.h>

int main() {
    int a[20] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39};
    int num;
    scanf("%d", &num);
    int low = , high = 19, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] == num) {
            printf("该数在数组中的位置是：%d\n", mid + 1);
            break;
        } else if (a[mid] < num) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    if (low > high) {
        printf("no found\n");
    }
    return ;
}

### 回答2：
首先，我们需要从键盘输入一个整数。可以使用scanf()函数实现，如下所示：

int num;
scanf("%d", &num);

然后，我们需要定义一个整型一维数组a，大小为20，如下所示：

int a[20];

接下来，我们需要从键盘输入20个整数，将它们存储到a数组中。可以使用for循环和scanf()函数实现，如下所示：

for(int i=0; i<20; i++){
scanf("%d", &a[i]);
}

现在，我们已经将20个整数存储到了a数组中。接下来，我们需要使用折半查找法找出输入的整数在a数组中的位置。折半查找法是一种高效的查找算法，算法的基本思路如下所示：

1. 将数组a按照从小到大的顺序排列；
2. 通过比较中间元素和目标值，缩小查找范围；
3. 重复第2步，直到找到目标值或者查找范围缩小到0。

下面是使用折半查找法实现的代码：

int left = 0;
int right = 19;
int mid;
while(left <= right){
mid = (left + right) / 2;
if(a[mid] == num){
printf("该数是数组中第%d个元素的值\n", mid+1);
break;
}
else if(a[mid] > num){
right = mid - 1;
}
else{
left = mid + 1;
}
}
if(left > right){
printf("no found\n");
}

最后，我们可以根据返回结果判断输入的整数是否在a数组中，如果在则输出该数是数组中第几个元素的值，否则打印”no found”提示信息。

### 回答3：
折半查找法是一种高效的查找算法，也称为二分查找法，利用了有序数组的特性，不断缩小查找范围进行查找。

具体实现过程如下：

1. 从键盘输入一个整数num作为查找目标；
2. 创建一个大小为20的整型数组a，并从键盘输入20个整数存入数组中；
3. 对数组a进行排序，确保数组有序；
4. 定义变量left和right分别表示查找范围的左右边界，初值分别为0和19；
5. 当left<=right时，执行以下操作：
a. 获取中间索引mid的值，mid=(left+right)/2;
b. 判断a[mid]与num的大小关系，如果a[mid]==num，则表示找到了目标，返回mid；
c. 如果a[mid]>num，则目标值在左半部分，将right指向mid-1；
d. 如果a[mid]<num，则目标值在右半部分，将left指向mid+1；
6. 如果整个循环结束后仍未找到目标值，输出"no found"。

下面是具体的代码实现：

#include <stdio.h>

// 折半查找法在有序数组a中查找num，返回查找结果
int binary_search(int a[], int num, int len) {
    int left = 0;  // 查找范围的左边界
    int right = len - 1;  // 查找范围的右边界
    
    while (left <= right) {
        int mid = (left + right) / 2;  // 计算中间位置
        if (a[mid] == num) {
            return mid;  // 找到目标值，返回索引
        } else if (a[mid] > num) {
            right = mid - 1;  // 目标值在左半部分，缩小右边界
        } else {
            left = mid + 1;  // 目标值在右半部分，扩大左边界
        }
    }
    
    return -1;  // 未找到目标值
}

int main() {
    int a[20];  // 定义大小为20的整型数组
    int num;  // 待查找的目标值
    int index = -1;  // 查找结果
    
    printf("请输入20个整数，以空格分隔：\n");
    for (int i = 0; i < 20; i++) {
        scanf("%d", &a[i]);  // 从键盘输入20个整数存入数组
    }
    
    // 对数组a进行排序
    for (int i = 0; i < 19; i++) {
        for (int j = 0; j < 19 - i; j++) {
            if (a[j] > a[j+1]) {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
    
    printf("请输入待查找的整数：");
    scanf("%d", &num);
    
    index = binary_search(a, num, 20);  // 在数组a中查找num
    
    if (index == -1) {
        printf("no found\n");
    } else {
        printf("%d是数组中的第%d个元素。\n", num, index + 1);
    }
    
    return 0;
}