折半查找算法（C语言实现）

折半查找法基本思路：折半查找的前提条件是对一组已经排过序的数据进行查找，取中间位置的元素与需要查找的数据进行比较。

如果相等，则返回中间元素的下标；如果大于，则从左边的区间查找，与该区域的中值进行比较；如果小于，则从右边的区间查找，与该区域的中值进行比较；

重复上述操作，直到找到目标数据为止，或者已经没有数据可以分区，表示没有找到。每次减少一半的查找范围，提高了查找效率。

如果数组的元素范围分别是 low 和 high，此时的中间元素是（low+high）/2。

在进行查找时，可以分成以下 3 种情况。

• 如果查找关键值小于数组的中间元素，关键值在数据数组的前半部分。
• 如果查找关键值大于数组的中间元素，关键值在数据数组的后半部分。
• 如果查找关键值等于数组的中间元素，中间元素就是查找的值。

示例

折半查找。C语言编程代码如下：

#include <stdio.h>
#include <stdlib.h>
#define MAX 21               /*最大数组容量*/
struct element
{  int key;};
typedef struct element record;
record data[MAX]={ 1,3,5,7,9,21,25, 33,46,89,100,121, 127,139,237,279,302,356,455,467,500}; /* 结构数组声明*/
/*折半查找*/
int binarysearch(int key)
{
    int low,high,mid;         /*数组开始、结束和中间变量*/
    low=0;                  /*数组开始，标记查找下限*/
    high=MAX-1;             /*数组结束，标记查找上限*/
    while(low<=high)
    {
        mid=(low+high)/2;        /*折半查找中间值*/
        if(key<data[mid].key)    /*当待查找数据小于折半中间值*/
             high=mid-1;        /*在折半的前一半重新查找*/
        else
        if(key>data[mid].key)    /*当待查找数据大于折半中间值*/
            low=mid+1;          /*在折半的后一半重新查找*/
        else
            return mid;         /*找到了，返回下标*/
    }
    return -1;                  /*没有找到返回-1*/
}
int main()
{
    int i,found;                  /*是否找变量*/
    int value;                  /*查找值*/
    printf("已经给出的21个数据为：\n");
    for(i=0;i<21;i++)
        printf("%d  ",data[i]);
    printf("\n");
    while(1)
    {
        printf("\n请输入查找值0~500(输入-1结束):");
        scanf("%d",&value);
        if(value !=-1)
        {
            found=binarysearch(value);  /*调用折半查找*/
            if(found!=-1)
                printf("找到查找值:%d[第%d个]\n",value,found+1);
            else
                printf("没有找到查找值:%d\n",value);
        }
        else
            exit(1);                  /*结束程序*/
    }
    return 0;
}

运行结果：

已经给出的21个数据为：
1  3  5  7  9  21  25  33  46  89  100  121  127  139  237  279  302  356  455  467  500

请输入查找值0~500(输入-1结束):21
找到查找值:21[第6个]

请输入查找值0~500(输入-1结束):95
没有找到查找值:95

请输入查找值0~500(输入-1结束):-1

折半查找的前提是数组已经按照大小顺序排列，本例是从小到大的排列顺序。

用户输入查找值，调用折半查找函数binarysearch()，以数组的下标居中的元素为中间值，把数组一分为二，根据查找值和中间值的大小关系，决定继续在上半部分还是下半部分查找，然后再次取下标居中的元素为中间值循环判断，直至找到查找值。