csdn每日一练——有序表的折半查找

问题描述：

用有序表表示静态查找表时，通常检索函数可以用折半查找来实现。

折半查找的查找过程是：首先确定待查记录所在的范围，然后逐步缩小范围直到找到或者确定找不到相应的记录为止。而每次需要缩小的范围均为上一次的一半，这样的查找过程可以被称为折半查找。

第二行包含n个用空格隔开的正整数，表示n个有序的整数。输入保证这n个整数是从小到大递增的。

第三行包含k个用空格隔开的正整数，表示k次查询的目标。

输出：

只有1行，包含k个整数，分别表示每一次的查询结果。如果在查询中找到了对应的整数，则输出其相应的位置，否则输出-1。

请在每个整数后输出一个空格，并请注意行尾输出换行。

以下程序实现了这一功能，请你填补空白处的内容：

#include <stdio.h>
int binary(int* a, int key, int n)
{
    int left = 0, right = n - 1, mid = 0;//第一次查询的left=0,n=19
    mid = (left + right) / 2;//第一次二分
    while (left < right && a[mid] != key)
    {
        if (a[mid] > key)//当目标值在中值左边，让此时的中值前一位的序号作为右值序号
        {
            right = mid - 1;
        }
        else if (a[mid] < key)//当目标值在中值右边，让此时的中值后一位的序号作为左值序号
        {
            left= mid +1;
        }
        mid = (right + left) / 2;//第二次算出中值，可一直循环
    }
    if (a[mid] == key)
        return mid;
    return -1;
}
int main(void)
{
    int Base_a[20] = { 1, 3, 5, 8, 9, 40, 120, 123, 125, 150, 199, 200, 1250, 1255, 1900, 2000, 2001, 3000, 3950, 5000 };
    int Search_a[5] = { 12, 199, 9, 2001, 3500 };
    int result = 0x00;
    for (int i = 0; i < sizeof(Search_a) / sizeof(Search_a[0]); i++)//sizeof(Search_a) / sizeof(Search_a[0])可获取要查询数组的长度
    {
        result = binary(Base_a, Search_a[i], sizeof(Base_a) / sizeof(Base_a[0]));//获取整个待索引数组的长度，为20，n=19
        printf("[%d %d] ", Search_a[i], result);//输出[目标元素，元素下标]，result有-1和mid两种取值方法
    }
    printf("\n");
    return 0;
}

 

 

 说明：感觉这个跟二分法原理一致，我写的注释可能有错误，如有发现，请指出，如果对你有帮助的话，点个赞鼓励一下吧！