LV020-二分查找

一、二分查找

1. 查找方法

二分查找也叫作折半查找，在某些情况下相比于顺序查找，效率会更高。但是该算法的使用的前提是静态查找表中的 数据必须是有序的。

算法思路：对给定值 k ，逐步确定待查记录所在区间，每次将搜索空间减少一半(折半)，直到查找成功或失败为止。

设两个游标 low 、 high ，分别指向当前待查找表的上界(表头)和下界(表尾)， mid 指向中间元素。中间元素按下面的公式计算：

$$mid=[\frac{low+high}{2}]$$

很多时候， mid 计算出来并不为整数，所以还需要进行 取整 操作。

整体过程如下图所示：

2. 函数实现

int Binsearch(seqlist r, keytype k)    /* 对有序表 r 折半查找的算法 */
{  
    int low, high, mid;  
    low = 1;
	high = r.len; 
    while (low <= high)    
    {  
        mid = (low+high) / 2;   
        if (k == r.data[mid].key)  
            return (mid);  
        if (k < r.data[mid].key) 
            high = mid - 1;  
        else 
            low = mid + 1;
    }      
     return 0;
 }

3. ASL

折半查找的运行过程可以用二叉树来描述，这棵树通常称为判定树。把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树，由此得到的二叉树，称为描述 二分查找的判定树( Decision Tree )或比较树。

二叉判定树怎么画？长度为 n 的查找表二叉判定树构造方法：

（1）当 n = 0 时，二分查找判定树为空；

（2）当 n ＞ 0 时，二分查找判定树的根结点是查找表中序号为 mid = (1 + n) / 2 的记录，根结点的左子树是与有序表 L [1] ~ L [mid - 1] 相对应的折半查找判定树，根结点的右子树是与 L [mid + 1] ~ L [n] 相对应的二分查找判定树。

假设表长 $n=2^h-1$，$h={\log }_2(n+1)$，记录数 n 恰好为一棵 h 层的满二叉树的结点数，则得出的判定树如上图。此时有：

$$ASL=\sum _{i=1}^n{P}_i{C}_i=\frac{1}{n}\sum _{i=1}^{h}i·2^{i-1}$$$$\text{令}S=\sum _{i=1}^{h}i·2^{i-1}=1·2^0+2·2^1+3·2^2+...+(h-2)·2^{h-2}+(h-1)·2^{h-1}$$$$\text{则}2S=2·\sum _{i=1}^{h}i·2^{i-1}=1·2^1+2·2^2+3·2^3+...+(h-2)·2^{h-1}+(h-1)·2^h$$$$\text{则}S=2S-S=h·2^h-(2^0+2^1+2^2+...+2^{h-2}+2^{h-1})=h·2^h-(2^h-1)=(n+1){\log }_2(n+1)-n$$$$\text{所以}ASL=\frac{n+1}{n}{\log }_2(n+1)-1$$

二分查找法的平均查找长度显然要比顺序查找方法更优。