折半查找的算法思想

折半查找又称二分查找，它仅适用于有序的顺序表。

基本思路是：首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如，在查找表升序排列时，若给定值key大于中间元素的关键字，则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

折半查找的实现

typedef struct{ //查找表的数据结构（顺序表）
    ElemType *elem; //动态数组基址
    int TableLen; //表的长度
}SSTable; 

//折半查找
int Binary_Search(SeqList L, ElemType key)
{
    int low=0, high=L.TableLen-1, mid;
    while(low<=high)
    {
        mid=(low+high)/2; //取中间位置
        if(L.elem[mid]==key)
            return mid; //查找成功则返回所在位置
        else if(L.elem[mid]>key)
            high=mid-1; //从前半部分继续查找
        else
            low=mid+1; //从后半部分继续查找
    }
    return -1; //查找失败，返回-1
}

查找效率分析

因为折半查找需要方便地定位查找区域，所以适合折半查找的存储结构必须具有随机存取的特性。因此，该查找法仅适合于线性表的顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。


从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数。

折半查找判定树的构造

折半查找的过程可用二叉树来描述，称为判定树。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值。








由上述分析可知，用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时，查找成功的平均查找长度为


树中最下面的叶结点都是方形的，它表示查找不成功的情况。

每个结点值均大于其左子结点值，且均小于于其右子结点值。

若有序序列有n个元素，则对应的判定树有n个圆形的非叶结点和n+1个方形的叶结点。

折半查找的查找效率

h是树的高度，并且元素个数为n时树高h=⌈log₂(n+1)⌉。所以，折半查找的时间复杂度为O(log₂n)，平均情况下比顺序查找的效率高。

拓展思考