(56)王道数据结构-折半查找

基本概念

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

基本思路是：
1.在[low,high]之间找目标关键字，每次检查mid = (low+heigh)/2
2.根据mid所指元素与目标关键字的大小调整low或high，不断缩小low和high的范围
3.若low > high则查找失败

代码逻辑

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
}

判定树

构造方法

1.由mid所指元素将原有元素分割到左右子树中
2.key: 右子树结点树 - 左子树结点树其中值为0或1

特性

1.折半查找的判定树是平衡的二叉排序树(左<中<右)

2.折半查找判定树，只有最下面一层是不满的

3.若查找表有n个关键字，则失败结点有n+1个

4.树高h = [log2(n+1)](不包含失败结点)

时间复杂度: O(log2n)