第七章 查找 三、折半查找（二分查找）

一、代码实现

此代码只能用于查找有序的顺序表

typedef struct {
    int *e;
    int len;
}SSTable;
 
int Search_Seq(SSTable st,int t){
    int i=0,j=st.len-1,mid;
    while (i<=j){
        mid=(i+j)>>2;
        if (t>st.e[mid]){
            i=mid+1;
        } else if (t
            j=mid-1;
        } else{
            return mid;
        }
    }
    return -1;
}

二、查找效率分析

在上图的查找判定树中，因为它的判定条件是mid = 「(low + high)/2]向上取整。

所以，右子树结点 - 左子树结点 = 0 或 1；

树高 h =log2(n+1)，不包含失败节点。

如果包含失败节点的话，树高为h+1；