二分查找

· · 个人记录

【概述】

二分查找又称折半查找，其要求线性表中的记录必须按\color{red}\text{关键码有序}，且必须采用顺序存储。

其基本思想是：用给定值 k 先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据 k 与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

【实现】

1.查找元素

int BinarySearch(int a[],int x,int x){
    int left,right,mid;
    int res=-1;

    left=0;//left为集合下界
    right=n-1//right为集合上界

    while(left<=right){
        mid=(left+right)/2;//设置中值
        if(num[mid]==x){//查找到符合元素x
            res=mid;
            break;
        }
        else if(num[mid]<x)//x在右边部分
           low=mid+1;//调整集合下界
        else//x在左边部分
           high=mid-1;//调整集合上界
    }
    return res;//若未找到x，则res= -1
}

图例

2.查找连续函数

bool cal(int x){
    ...
}
int BinarySearch(double low,double high){//low为区间下界，high为区间上界
    double left,right,mid;
    left=low;//设置当前查找区间上界的初值
    right=high;//设置当前查找区间下界的初值

    while(right-left>1.0e-6){
        mid=(right+left)/2;//设置中值
        if(cal(mid)<x)//函数结果小于带查找的值
            left=mid;//说明在右边部分，调整集合下界
        else
            right=mid;//说明在左边部分，调整集合上界
    }
    return mid;
}

【二分查找判定树】

对表中每个记录的查找过程，可用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置，常将这个描述二分查找过程的二叉树称为\color{blue}\text{二分查找判定树}。

1.构造

当 n=0 时，折半查找判定树为空

当 n>0 时，折半查找判定树的根结点为 mid=(n+1)/2，根结点的左子树是与有序表 r[1] ~ r[mid-1] 相对应的折半查找判定树，根结点的右子树是与 r[mid+1] ~ r[n] 相对应的折半查找判定树。 

2.性质

任意两棵折半查找判定树，若它们的结点个数相同，则它们的结构完全相同

具有n个结点的折半查找树的高度为 \text{ }\left\lfloor log_2\:n\right\rfloor+1\text{ } 

任意结点的左右子树中结点个数最多相差 1

任意结点的左右子树的高度最多相差 1

任意两个叶子所处的层次最多相差 1

【复杂度分析】

最坏情况下，关键码比较次数为 log2(n+1)，时间复杂度为 O(logn)

在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。

具有 n 个结点的二分查找判定树的深度为\text{ }\left \lfloor log_2\:n \right \rfloor+1\text{ } ，因此当查找成功时，所进行的关键码比较次数至多为\text{ }\left \lfloor log_2\:n \right \rfloor+1\text{ }，而查找不成功时，就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数，即失败情况下的平均查找长度等于树的高度。

以深度为 k 的满二叉树为例，其深度为：\text{ }n=2^k-1\text{ }，树上的第 i 层有:\text{ }2^{i-1}\text{ } 个结点，假设表中的每条记录查找概率相等，即：\text{ }p_{i}=\frac{1}{n} \text{ }

则有：\text{ }ASL=\sum_{i=1}^np_ic_i=\frac{1}{n}\sum_{j=1}^kj*2^{j-1}=\frac{1}{n}(1*2^0+2*2^1+...+k*2^{k-1})\approx log_2(n+1)-1

故平均时间复杂度为：O(logn)