二分查找（折半查找）

二分查找又称折半查找，前提要求数据序列呈现线性结构，即必须是经过排序的。

基本思路：

      在一组有序序列中，取中间值与给定关键字进行比较，如果给定关键字大于该值关键字，则要查找的关键字位于有序序列的后半部分；若给定小于该值，则要查找的关键字位于有序序列的前半部分。每次将有序序列的长度缩小一半之后，再从中间位置的记录进行比较，依次反复进行。

查找过程如下：

1、查找初始化为low=1、high=length。其中low和high是两个位置指示器，分别指向当前序列的第一个和最后一个值；

2、对当前有序序列做如下处理：

（1）求当前序列的中间位置：mid=（low+length）/2，mid为中间值的位置指示器；

（2）将要查找的查询关键字与mid指示的值进行比较。若相等，查找结束，返回中间位置的值mid；若大于该值，则将查找范围缩短为该序列的后半部分，此时改变low=mid+1，而high值不变；若小于该值，则将查找范围缩短为该序列的前半部分，此时改变high=mid-1，而low值不变。

（3）重复执行过程（2）直至找到待查关键字，返回此值的位置mid，否则返回0。

#include<stdio.h>
#include<stdlib.h>

#define max_len 20

typedef struct
{
    int key;
    char data;
}Record;

typedef struct
{
    Record r[max_len+1];
    int length;
}seqTable;

int BinarySearch(seqTable st,int k)
{
    int low,high,mid;

    low=1;
    high=st.length;


    while(low<=high)
    {
        mid=(low+high)/2;
        
        if(st.r[mid].key<k)
            low=mid+1;
        else
        {
            if(st.r[mid].key>k)
                high=mid-1;
            else
                break;
        }
    }
    if(low>high)
        return 0;
    else
        return mid;
}

void main()
{
    seqTable st;
    int i;  
    int len; //定义变量为线性表的长度
    int ch;  //定义变量为线性表的输入参数
    int kk; //定义变量为查询关键字
    int res; //定义变量为查找函数返回值

    printf("二分查找演示操作！
");
    printf("输入线性表的长度：");
    scanf("%d",&len);

    st.length=len;
    printf("输入%d个记录的关键字值（用空格隔开）：
",len);
    for(i=1;i<=len;i++)
    {
        scanf(" %d",&ch);
        st.r[i].key=ch;
    }
    printf("输入查询关键字：");
    scanf("%d",&kk);
    res=BinarySearch(st,kk);
    
    if(res==0)
        printf("该查找表中不存在此记录！
");
    else
        printf("该记录位于该查找表中的第%d个！",res);

    printf("
");
    system("pause");

}

结果显示：