9-查找

折半查找

思想

折半查找思想，将给定值key和中间值进行比较，如果小于则查找左半边，大于则查找右半边。当不满足low<high的时候会结束查找，最终显示查找失败。折半不适用于链式存储 直接看算法：

int Binary_Search(int a[],int key){
    int len = len(a);
    int low = 0;high = len - 1;
    while(low<=high){
        mid = (low + high)/2;
        if(mid == key)reutrn mid;
        if(mid < key){
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    return 
}

构造二叉树

计算成功ASL和失败ASL

1）成功： 层数乘以结点数求和再除以长度成功ASL为： $\frac{1*1+2*2+3*4+4*4}{11}$ 2）失败：

将图中的二叉树补上结点，原来的每个叶子结点都补成度为2的结点
这些失败结点是虚拟的，实际是不存在的，所以计算的时候，层数是按它的父节点来计算

所以图中的失败ASL为： $\frac{3*4+4*8}{12}$ 这里的12是失败结点。

分块查找

分块查找综合了顺序查找和折半查找的优点，将数据分组，组内可以无序，但是组间必定有序，然后分别记录各组内的最值key。查找的时候先找最值Key，再按分组指针去顺序查找。下图举例：

ASL

1）成功 先找到分块的key节点，计数一次，然后去块间顺序查找，依次+1 2）失败 整体失败的情况无法预估，题目更可能考察某一个点的查找失败，与成功类似，块间顺序查找完全部元素，即为查找失败，其实就是块长+1

散列查找

基本概念

一种特殊的数据结构，能够根据元素关键字计算出他在散列表中的存储地址

散列函数

散列哈希函数： $Addr = H(key)$ 建立起关键字和散列地址的映射关系，408一般考察除留余数法。散列表表长是m，取不大于m的最大质数p，构建函数 $H(key) = key \% p$ ，则产生的地址落在区间 $[0,p-1]$ **处理冲突：**冲突是指经过散列函数映射的地址上已经有关键字，则需要采取一定处理办法解决冲突。如下解决冲突办法：

开放地址法

1、线性探测：一个一个向下探测，按 $d_i = 0,1,2...$ 进行探测 2、平方探测（二次探测法）：按照 $d_i = 0^2,1^2,-1^2,2^2,-2^2.........k^2,-k^2$ ，其中 $k \le m/2$ ，散列表长度m必须是一个可以表示成4k+3的素数 3、双散列两个散列函数： $H_i = (H(key)+i*Hash_2(key)) \% m$ 4、伪随机序列法当 $d_i$ 为伪随机数序列时候

拉链法

一张图理解

查找成功和失败

查找成功是针对关键字的，计算出查找每个关键字查找成功的次数，除以关键字个数即可
查找失败是针对散列函数的，由散列函数的质数p可知:散列地址在 $[0,p-1]$ 所以失败针对这些散列地址，依次计算这些地址查找失败的次数，累加除以p即可

折半查找​

思想​

构造二叉树​

计算成功ASL和失败ASL​

分块查找​

ASL​

散列查找​

基本概念​

散列函数​

开放地址法​

拉链法​

查找成功和失败​