本章我们学了一下几种查找方法

• 顺序查找法
• 分块查找法
• 折半查找法
• B树及其基本操作
• B+树的基本概念
• 散列(Hash)表
• 字符串模式匹配

内部查找

一般对于内存中一个序列的数字集合的查找，我们采用下面几种查找方式

顺序查找，时间复杂度O(N),
分块查找，时间复杂度O(logN+N/m);
折半查找，时间复杂度O(logN)
哈希查找，时间复杂度O(1)

外部查找

我们都知道二叉查找树的查找的时间复杂度是Ｏ(log N)，其查找效率已经足够高了，那为什么还有Ｂ树和Ｂ＋树的出现呢？难道它两的时间复杂度比二叉查找树还小吗？
答案当然不是，Ｂ树和Ｂ＋树的出现是因为另外一个问题，那就是磁盘ＩＯ；众所周知，ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。
所以，我们为了减少磁盘ＩＯ的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。一个基本的想法就是：
（1）、每个节点存储多个元素
（2）、摒弃二叉树结构，采用多叉树

这样就引出来了一个新的查找树结构 ——多路查找树。 根据AVL给我们的启发，一颗平衡多路查找树(B-树)自然可以使得数据的查找效率保证在O(logN)这样的对数级别上。

字符串查找

前面我们主要是针对单个元素的查找，如果我们是想找到一段数据的话，就需要对字符串进行匹配。

一般我们采用简单的模式匹配算法或者KMP模式匹配算法

小结

查找的方法虽然很多，但是我们需要根据特定的情况去选择最合适的算法。

课后习题

【2016年真题】在有n(n>1000)个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示。

k = 0;  
while (k < n 且 A[k] < x) k = k + 3;  
if (k < n 且 A[k] == x)查找成功;  
else if (k-1 < n 且 A[k-1] == x)查找成功;  
else if (k-2 < n 且 A[k-2] == x)查找成功;  
else 查找失败;  

本算法与折半查找算法相比，有可能具有更少比较次数的情形是（）
A.当x不在数组中            B.当x接近数组开头处
C.当x接近数组结尾处        D.当x位于数组中间位置

参考答案：B

【2013年真题】设包含 4 个数据元素的集合 S={ "do"，"for"，" repeat"，" while"}，各元素的查找概率依次为：p1=0.35，p2 = 0.15，p3=0. 15，p4=0.35。将 S 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 2.2。请回答： 
（1）若采用顺序存储结构保存 S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？ 
（2）若采用链式存储结构保存 S，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

参考答案：
（1）采用顺序存储结构，数据元素按其查找概率降序排列。
采用顺序查找方法。
查找成功时的平均查找长度= 0.35×1+0.35×2+0.15×3+0.15×4=2.1。
（2）
【答案一】 
采用链式存储结构，数据元素按其查找概率降序排列，构成单链表。 
采用顺序查找方法。
查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。
【答案二】 
采用二叉链表存储结构，构造二叉排序树，元素存储方式见下图。

采用二叉排序树的查找方法。
查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。

【2011年真题】一个长度为 L（L≥1）的升序序列 S，处在第L/2个位置的数称为 S 的中位数。 例如，若序列 S1=（11,13,15,17,19），则 S1 的中位数是 15，两个序列的中位数是含它 们所有元素的升序序列的中位数。例如，若 S2=（2,4,6,8,20），则 S1 和 S2 的中位数是 11。现在有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求： 
（1）给出算法的基本设计思想。 
（2）根据设计思想，采用 C 或 C++或 JAVA 语言描述算法，关键之处给出注释。 
（3）说明你所设计算法的时间复杂度和空间复杂度。 

解答： 
（1）算法的基本设计思想如下。 
分别求出序列 A 和 B 的中位数，设为 a 和 b，求序列 A 和 B 的中位数过程如下： 
1）若 a=b，则 a 或 b 即为所求中位数，算法结束。 
2）若 a<b，则舍弃序列 A 中较小的一半，同时舍弃序列 B 中较大的一半,要求舍弃的长度相等； 
3）若 a>b，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求舍弃的长度相等； 
在保留的两个升序序列中，重复过程 1）、2）、3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。 
（2）算法的实现如下： 

int M_Search(int A[],int B[],int n){  
    int s1=0,d1=n-1,m1,s2=1,d2=n-1,m2;  
    //分别表示序列 A 和 B 的首位数、末位数和中位数  
    while(s1!=d1||s2!=d2){  
        m1=(s1+d1)/2;  
        m2=(s2+d2)/2;  
        if(A[m1]==B[m2])   
            return A[m1]; //满足条件 1）  
        if(A[m1]<B[m2]){ //满足条件 2)  
            if((s1+d1)%2==0) { //若元素个数为奇数  
                s1=m1; //舍弃 A 中间点以前的部分且保留中间点  
                d2=m2; //舍弃 B 中间点以后的部分且保留中间点  
            }  
            else{ //元素个数为偶数  
                s1=m1+1; //舍弃 A 中间点及中间点以前部分  
                d2=m2; //舍弃 B 中间点以后部分且保留中间点  
            }   
        }  
        else{ //满足条件 3）  
            if((s1+d1)%2==0) { //若元素个数为奇数  
                d1=m1; //舍弃 A 中间点以后的部分且保留中间点  
                s2=m2; //舍弃 B 中间点以前的部分且保留中间点  
            }  
            else{ //元素个数为偶数  
                d1=m1+1; //舍弃 A 中间点以后部分且保留中间点  
                s2=m2; //舍弃 B 中间点及中间点以前部分  
            }   
        }   
    }  
    return A[s1]<B[s2]? A[s1]:B[s2];  
}  

（3）算法的时间复杂度为 O(log₂n)，空间复杂度为 O(1)。