二分查找

一、原理
        二分查找要求线性表中的结点必须按照关键字值得递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字进行比较，这个中间结点把线性表分成了两个子表，若比较结果相等则查找完成；若不相等，再根据k与该结点关键字的比较大小确定下一步查找哪个子表，这样递归进行下去，直到找到满足条件的结点或者该线性表中没有这样的结点。

二、算法
1、数据结构
        typedef struct element
        {
            KeyType key;
            ElemType data;
        }sqlist;
       这里KeyType和ElemType可以是任何数据类型，比如int、float或者char等，在算法中，我们约定其默认类型是int。
2、算法实现
        二分查找的函数如下，其功能是在线性表r中二分查找关键字为k的结点，若找到了，返回其位置i；若找不到，返回-1：
        int binsearch(sqlist *r, int k, int n)
       {
            int i=0, low=0, high=n-1, mid=0, find=0;
            while ((low <= hight) && (!find))
            {
                 mid = (low + high)/2;
                 if (k < r[mid].key)
                 {
                      high = mid - 1;
                 }
                 else if (k > r[mid].key)
                 {
                      low = mid + 1;
                 }
                 else
                 {
                      i = mid;
                      find = 1;
                 }
            }
            if (!find)
            {
                i = -1;
            }
            return i;
       }
       参数r为线性表，k为待查找关键字，n为线性表中元素个数。