目录

一、前言

基本概念：

二、基于线性表的查找法

1.顺序查找法

2.二分查找法

3.分块查找法

三、基于树的查找法

1.二叉排序树

2.平衡二叉树

3.B_树

一、前言

        在非数值运算过程中，数据存储量一般很大，为了在大量的信息中找到某些值，就需要查找技术。而不同的查找方法，会直接影响到算法的有效性，接下来主要学习两大类查找方法，分为：比较式和计算式，其中比较式可以分成基于线性表和基于树，计算式也称为哈希法。

基本概念：

• 查找(Search)：也称检索，是根据给定的某个值，在查找表中确定一个关键字等于给定值的数据。
• 关键字：标识列表中一个或一组数据元素，唯一标识一个数据可以称为主关键字（如数组的上标）
• 平均查找长度ASL：为了在表中找到所给元素，比较次数的期望值叫平均查找长度。

知识框架： 

二、基于线性表的查找法

1.顺序查找法

        从表的第一个元素开始检索，将要查找的值与表中的数据一一对比，找到则查找成功，否则查找失败。

          以上图为例，在线性表的首位给定64并设为监视哨，从后往前依次比较，比较五次后找到。对于平均查找长度

编码实现：

int SeqSearch(RecordList  l,  KeyType  k)

{
	int i; i=l.length;
     l.r[0].key=k;                       
    while (l.r[i].key!=k)  i--;     
	return(i);
}

总结：

• 适合较短的有序表或无序表
• 时间复杂度O(n)

2.二分查找法

        二分查找又称为折半查找法，首先选择表中间的一个记录，比较其关键字的值，若要找的记录的关键字值大，则再取表的后半部的中间记录进行比较；否则取前半部的中间记录进行比较，如此反复，直到找到为止。

        具体的算法描述为，定义low=1指向表头，high=n指向表尾,mid=(low+high)/2,让指向的值与mid比较，分为三种情况：

1.如果相等，则查找成功

2.比mid指向的值大，low=mid+1,再次比较

2.比mid指向的值小，high=mid-1,再次比较

最后，low>high，查找失败

编码实现： 

int BinSrch(RecordList  l,  KeyType  k)

{
	int low,high,mid;
	low=1;   high=l.length;     
	while( low <= high)
	{
		mid=(low+high) / 2;      
		if  (k==l.r[mid]. key)  return (mid);   
		else  
		   if (k 
  总结：
 
适合有序表       
平均查找长度最小     ASL=(n+1)/n * log2（n+1） -1                 ASL≈log2（n+1） -1  (N>50)
时间复杂度 O（log2n）                 
3.分块查找法 
将n个元素分成几块，块内的元素可以无序，但必须确定一个最大值或者最小值，以此形成索引表，例如下面的一个分块表：
 
 
 要查找38先在索引表中确定在哪一块，38比22大，48小应该在第二块，在第二块进行顺序查找。
 
对于块查找算法不做要求，主要特点为：
 
平均查找长度比线性查找小
用二分法时 ASL=
用顺序查找时  ASL=
三、基于树的查找法 
1.二叉排序树 
 
 
二叉排序树（也称二叉查找树）或是一棵空树，或是具有下列性质的二叉树：
 
 
它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
 它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
 左、右子树也分别为二叉排序树          
 
二叉树生成原则：
 
           若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子。          
 
 二叉排序树的生成演示如下图：
 
 
 对于二叉排序树的平均查找长度,例如由1，2，3，4，5构建的二叉树
 
ASL=（3+2+1+2+3）/5=3
 
2.平衡二叉树 
        平衡二叉树又称为AVL树，它的左子树和右子树都为AVL树，并且|左子树-右子树|<=1。
 
       高度不平衡                                                                     高度平衡
 
                           
 
3.B_树 
         由R.Bayer和E.Maccreight于1970年提出的，是一种特殊的多叉树，是一种在外存文件系统中常用的动态索引技术，是大型数据库文件的一种组织结构，B-树中的每个结点大小都相同。
 
 
 
 
 m称为B-树的阶，m≥3，根结点至少有 2 个子树。
 
 K1、K2、…Kn为n个按从小到大顺序排列的关键字
 
 
对非根结点关键字范围m/2 -1≤n≤m-1 ，对根结点，1≤n≤m-1
 
 
结点子树范围为（m/2 ，m）m/2为向上取整