【数据结构——树表的查找（动态查找表）】

动态查找表（基于树的查找法）

当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录。
改用动态查找表——几种特殊的树
表结构在查找过程中动态生成。
对于给定值：
若表中存在，则返回成功；
否则，插入关键字等于key的记录

（一）二叉排序树

1、定义

二叉排序树又称二叉查找树
定义：
二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：
实例——判断二叉排序树

二叉排序树的存储结构：二叉链表表示

//二叉排序树的存储结构
typedef struct
{
	KeyType key;					//关键字项
	InfoType otherinfo;				//其他数据项
}ElemType;							//每个结点的数据域的类型

typedef struct BSTNode
{ //结点结构
	ElemType data;					//数据域
	struct BSTNode* lchild, * rchild;	//左右孩子的指针
}BSTNode,*BSTree;

2、查找算法

算法思想

算法描述

typedef struct BSTNode
{ //结点结构
	ElemType data;					//数据域
	struct BSTNode* lchild, * rchild;	//左右孩子的指针
}BSTNode,*BSTree;

BSTree SearchBST(BSTree T, KeyType key)
{
	//在指针T所指的二叉排序树中递归地查找某关键字等于key的数据元素
	//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
	if (!T || key == T->data.key)
		return T;					//查找结束
	else if (key < T->data.key)
		return SearchBST(T->lchild,key);//在左子树中继续查找
	else
		return SearchBST(T->rchild,key);//在右子树中继续查找
} 

二叉排序树的查找分析：
（1）在二叉排序树上查找其他关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程。
比较的关键字次数=次结点所在的层次数
最多比较次数=树的深度
（2)但 二叉排序树平均查找长度和树的形态有关

3、插入算法

typedef struct BSTNode
{ //结点结构
	ElemType data;					//数据域
	struct BSTNode* lchild, * rchild;	//左右孩子的指针
}BSTNode, * BSTree;

//二叉排序树的插入
void InsertBST(BSTree& T, ElemType e)
{//当二叉排序树T中不存在关键字等于e.key的数据元素时，则插入该元素
	if (!T)							//T为空树
	{ //找到插入位置，递归结束
		BSTree S;
		S = new BSTNode;			//生成新结点*S
		S->data = e;				//新结点数据域置为e
		S->lchild = S->rchild = NULL;//新结点*S作为叶子结点
		T = S;						//把新结点*S链接到已找到的插入位置
	}
	else if (e.key < T->data.key)
		InsertBST(T->lchild, e);	//将*S插入左子树
	else if (e.key > T->data.key)
		InsertBST(T->rchild, e);	//将*S插入右子树
}

4、创建算法

typedef struct BSTNode
{ //结点结构
	ElemType data;					//数据域
	struct BSTNode* lchild, * rchild;	//左右孩子的指针
}BSTNode, * BSTree;

//创建
void CreatBST(BSTree& T)
{ //依次读入一个关键字为key的结点，将此结点插入到二叉排序树T中
	T = NULL;						//将二叉排序树T初始化为空树
	cin >> e;
	while (e.key != ENDFLAG)
	{ //ENDFLAG为自定义常量，作为输入结束标志
		InsertBST(T, e);			//将此结点插入到二叉排序树T中
		cin >> e;
	}
}

5、删除算法

（1）被删除结点*p为叶子结点

（2）被删除结点*p只有左子树或者只有右子树

实例：

（3）被删除结点*p既有左子树又有右子树

实例

例：

算法描述：

//在这里插入代码片

（二）平衡二叉树

1、平衡二叉树的定义

平衡二叉树又称AVL树
一棵AVL树或者是空树，或者是具有下列性质的二叉排序树：
（1）它的左子树和右子树都是AVL树，且左子树和右子树的深度之差的绝对值不超过1
(2)左子树和右子树也是AVL树

···每个结点附加一个数字，给出该结点的平衡因子BF:该结点的左子树深度和右子树深度之差。
···AVL树任一结点平衡因子只能取-1，0，1

2、如何构造平衡二叉树

如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡

调整方法：找到离插入点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小不平衡子树，可将重新平衡的范围局限于这棵子树。

平衡调整的四种类型

LL型调整：


RR型调整：

LR型调整：

RL型调整：

3、AVL的插入

实例：

（三）B-树

1、B-树的概念

2、B-树的结点特点

3、B-树的特点

4、B-树的搜索算法

    动态查找表的特点是，表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。

    以上相当于是动态查找表的定义。在对数据库表进行插入/删除操作时，索引需要进行维护工作，也就是索引会动态的变化，而动态查找表能满足索引动态变化的要求。

    动态查找表包括二叉排序树、平衡二叉树（AVL树）、B树、B+树以及红黑树。下面对它们分别进行分析。

二叉排序树

    定义：是一颗空树；或者是具有下列性质的二叉树：

                1、若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值。

                2、若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。                

                3、它的左、右子树也分别为二叉排序树。      

                  

                                      上图为一颗二叉排序树

    实现：通常使用二叉链表实现，也可使用三叉链表等方式。

    查找：在进行查找时，首先将给定值与根节点的关键字比较，若相等则查找成功，否则根据给定值和根节点的关键字之间的大小关系，分别在左子树或右子树上继续查找。

    插入：插入是在查找不成功后才进行的操作，所以新插入的结点一定是树的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子，在判断之后直接插入到树中。

    容易看出，中序遍历二叉排序树能得到关键字的有序序列。此外，进行插入操作时，不必移动其它结点，仅需改动某个结点的指针，这就相当于在一个有序序列中插入一个记录而不需要移动其它记录。由此表明，二叉排序树拥有类似于折半查找的特性，而且使用链表作为存储结构，是动态查找表的一种合适表示。

    删除：删除分为三种情况：（删除p结点）

        1、p是叶子结点：删除叶子结点不破坏整棵树的结构，所以只需要修改p的父节点的指针即可。

        2、p只有左子树或只有右子树：直接令p的子树成为p的父节点的子树即可。

        3、p的左右子树均不为空：这时有两种做法：

            （1）令p的左子树代替p的位置，p的右子树则移动到p的左子树的最右端（即p的左子树的最右的结点）

            （2）找到p的左子树的最右端的结点（或p的右子树的最左端节点），代替p的位置，若该结点有左子树，则其左子树（右子树）代替该结 点原来的位置。具体请看下图：

                             

                           左侧为删除p结点前，中间为第一种删除方式，右侧为第二种删除方式

    二叉排序树的查找、插入、删除方式都已经了解完了，接下来该考虑的就是性能，或者说适不适合作为数据库索引的数据结构。

    二叉排序树在进行插入操作时不需要移动其它结点，插入效率能得到保证。并且查找采用类似于折半查找的方式，查找效率同样也不低。但是不能忽略了生成二叉排序树时产生的问题。例如：有两颗二叉排序树，分别由（45,24,53,12,37,93）与（12,24,37,45,53,93）生成，生成的两棵树如下图所示：

    从上图可以明显看出，二者的平均查找长度是有差异的，右侧二叉排序树的平均查找长度明显大于左侧。所以其平均查找长度会根据树的形态不同而产生不同程度的差异，是不稳定的，“不平衡”的，是不适合作为数据库索引的数据结构的。下面接着介绍“平衡”的二叉排序树。

平衡二叉树（AVL树）

    定义：是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。实际上就是在二叉排序树的基础上加上了，左右子树深度之差的绝对值不超过1的约束条件，来保证是平衡的二叉排序树。

    由于平衡二叉树只是在二叉排序树的基础上增加了约束条件，所以其实现方式与查找方式是与二叉排序树相同的。

     在介绍插入之前得讲一个实现二叉树平衡常用的操作：左旋及右旋，可以参考此处。

     插入：平衡二叉树插入过程与二叉排序树的插入过程一致，只是多出了保持平衡这一项。插入一个节点后，树可能变为不平衡的（即左子树和右子树的深度之差的绝对值超过了1），这时就要使用左旋及右旋操作使其恢复平衡。首先要找到最小不平衡子树，然后通过该子树的根节点来判断，分下列几种情况（该根节点为P，其左孩子为Pl，其右孩子为Pr，其左孩子的左右孩子为Pll、Plr，其右孩子的左右孩子为Prl、Prr）：

    （1）往该根节点的左孩子的左子树添加节点（LL）：以P与Pl为轴，进行右旋操作。

            

    （2）往该根节点的左孩子的右子树添加节点（LR）：以Pl与Plr为轴，进行左旋操作。然后重复一次操作（找到最小不平衡子树，判断属于哪种情况）。

            

    （3）往该根节点的右孩子的左子树添加节点（RL）：与情况（2）相同，只是方向不同。以Pr与Prl为轴，进行右旋操作。然后重复一次操作（找到最小不平衡子树，判断属于哪种情况）。

    （4）往该根节点的右孩子的右子树添加节点（RR）：与情况（1）相同，只是方向不同，以P与Pr为轴，进行左旋操作。

    删除：平衡二叉树与二叉排序树的删除相同，也是多出了保持平衡这一项，保持平衡可以参照平衡二叉树的插入。

    总的来说，平衡二叉树相较二叉排序树来说，其查找的稳定性远大于二叉排序树，代价是花出多余时间来维护二叉树的平衡。就目前来说，平衡二叉树已经适合作为数据库索引的数据结构的。但是随着数据量的增加，在进行插入与删除时会进行大量的平衡度计算，严重影响了性能。为了克服这个问题，下面介绍另一种平衡方式的“平衡”二叉树。

红黑树（下面图中均没有NIL，请大家自行脑补吧，画图不好画...）

    定义：红黑树也是在二叉排序树的基础上增加了平衡性约束，不过相较平衡二叉树而言，红黑树的约束条件没有平衡二叉树那么严格。

                1、节点是红色或黑色。

                2、根节点是黑色。

                3、每个叶节点（NIL节点，空节点）是黑色（约束：当一个黑色节点只有一个孩子时，该孩子为红色）。

                4、每个红色节点的两个子节点都是黑色。

                5、从任一节点到该节点每个叶子的所有路径都包含相同数目的黑色节点。如下图：

                                               

    插入：首先将红黑树当做二叉排序树进行插入，然后将节点重新着色保持平衡。假设插入节点为P，将插入节点着色为红色，此时要分三种情况：

    1、P为根节点，直接将P着色为黑色。

    2、P的父节点为黑色，此时插入后的树不会违背定义中的约束条件，仍为一颗红黑树，不需要做任何处理。

    3、插入节点的父节点为红色，此时违背了定义4（每个红色节点的两个子节点都是黑色），需要对树进行操作，使之重新成为一颗红黑树。（其核心思想就是将红色节点移到根节点，然后将其变为黑色）

    3、（1）P的父节点为红色，父节点的兄弟节点（叔叔节点）是黑色，P为其祖父节点的左孩子的左孩子时：以其祖父节点为支点进行右旋操作，然后将其父节点变为黑色，其祖父节点变为红色。如下图，插入节点12：

                    

          （2）P的父节点为红色，P的叔叔节点是黑色，P为其祖父节点的左孩子的右孩子时：以其父节点为支点，进行左旋操作，然后继续判断。如下图，插入节点14，操作完后变为了情况（1），按情况（1）继续操作即可：

                    

        （3）P的父节点为红色，P的叔叔节点是黑色，P为其祖父节点的右孩子的右孩子时：此时的处理方式与情况（1）相同，只是由右旋变为左旋。

          （4）P的父节点为红色，P的叔叔节点是黑色，P为其祖父节点的右孩子的左孩子时：此时的处理方式与情况（2）相同，只是由左旋变为右旋。

          （5）P的父节点为红色，P的叔叔节点也为红色时：将P的父节点和叔叔节点都设为黑色，将P的祖父节点设为红色，然后以P的祖父节点为当前节点（插入节点）继续判断。如下图：

    删除：红黑树的删除过程也与二叉排序树的过程相同，删除后再进行维护平衡的工作，详情见上面二叉排序树的删除，情况3时选择第二种删除方法，找到删除节点D右子树的最左节点X的值复制到D，此时删除的情况就转换为了删除X，如下图：

                                    

    至此，只用考虑删除叶子结点的情况了。

    假设要删除节点为D，其左右子树为Dl、Dr，其父节点为P，其兄弟节点为Pr，其兄弟节点的左右子树为Prl、Prr。D为最左节点，所以D的左子树Dl为空。下图是要考虑到的7种情况：

                                        

    1、D为红色：此时Dr必为空（由定义3、5可推断出），删除一个红色叶子结点不影响红黑树的“平衡”，此时直接将D删除即可。

    2、D为黑色，Dr不为空：此时Dr必为红色，使用Dr代替D，并变为黑色即可。

    D为黑色，Dr为空：此时删除D，P的左子树的黑色节点会减少一个，违背了定义5。为了保持“平衡”就需要从P的右子树中拿一个节点到P的左子树，以保证P的左子树的黑色节点个数。下面就对P及P的右子树的节点的颜色情况进行讨论：（下面的情形操作完后，树不一定恢复了平衡，若未恢复平衡，则继续以D为标志，判断当前属于哪种情况）

    3、Pr为红色：那么P、Prl、Prr一定都为黑色，绕P进行左旋操作，并交换P与Pr的颜色。

               

                

    4、Prl为红色，P和Prr为任意颜色：此时Pr必为黑色，Prr为红色或空（NIL节点），绕Pr右旋，Pr与Prl交换颜色。

                    

    5、Prr为红色，P和Prl为任意颜色：此时Pr必为黑色，Prl为红色或空（NIL节点），绕P左旋，交换P与Pr的颜色，Prr变为黑色。

                     

    6、P为红色，Prr和Prl为黑色：此时Pr必为黑色，Prl与Prr为空（NIL节点），P与Pr交换颜色。

                    

    7、P、Prr和Prl均为黑色：此时Prl与Prr为空（NIL节点），将Pr变为红色。

                    

    红黑树的查询性能会稍逊于AVL树，因为红色节点的存在不影响红黑树的“平衡”，所以红黑树在查询相同内容的情况下，最多比AVL树多一次比较。但是，在插入与删除上红黑树完胜AVL树，AVL树在每次插入删除的时候会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多。

    红黑树在插入后为了恢复平衡，最多进行两次旋转操作；在删除后为了恢复平衡，最多进行三次旋转操作。

    红黑树在查找、插入、删除的性能方面已经比较不错了。但是是不是适合作为数据库索引呢？下面来分析一下。

    当树存储在磁盘中时：红黑树在进行查找操作时，在树的每一层都会进行一次IO操作（取到对应的节点数据）。而红黑树是二叉树，当数据量非常大时，树的高度也会非常大。此时进行查找操作需要进行多次IO操作，而IO操作是十分耗时的，会造成查询效率低下。所以为了提升查询效率，需要减少IO操作，也就是需要降低树的高度，此时就引进来了B-Tree。

B树

    定义：假定树的度为D，则一颗B树需要满足以下条件：

                1、D > 2。

                2、根节点的儿子数为[2，D]。

                3、除根节点以外的非叶子节点的儿子数为[D/2，D]。

                4、每个节点存放的关键字个数：[D/2-1(向上取整)，D-1]。（根节点最少为1）

                5、非叶子节点：关键字个数 + 1 = 指针个数。

                6、节点关键字：k[1]、k[2]、、、k[n]，其中k[i] < k[i+1]。

                7、非叶子节点指针：p[1]、p[2]、、、p[n]，其中p[1]指向关键字小于k[1]的子树，p[2]指向关键字大于k[1]、小于k[2]的子树。

                8、所有叶子节点位于同一层。

    下图就为一颗度为3的B树：

    查找：B树的查找与二叉排序树、AVL树及红黑树的查找略有不同。B树是多叉树，所以会从左往右遍历该节点中所有的关键字，来确定在该节点的哪一个子树继续进行查找。

    插入：B树插入操作的基本步骤：

               1、根据要插入关键字的值，找到叶子节点并插入。

               2、判断当前节点的关键字个数是否大于D-1，若不满足则插入结束，若满足则执行3。

              3、以节点中间的关键字为中心分裂成左右两部分，将该关键字插入到父节点中，并将该关键字的左子树指向分裂后的左半部分，右子树指向分裂后的右半部分，然后继续执行2。

          下面介绍一个5阶B树的插入过程，依次插入（39，22，97，41，53，13，21，40，30，27，33 ，36，35，34 ，24， 29，26），因为是5阶B树，所以节点中最多有4个关键字。

           （1）插入39，22，97，41。

                                            

           （2） 插入53。

                                           

                      此时，节点中有5个关键字，大于4（D-1），所以以41为中心进行分裂。（若D为偶数，选择中心关键字时，从中间两个关键字任取一个即可）

                                            

           （3）插入13，21，40。

                                    

                     进行分裂。

                                      

           （4） 插入30，27，33 ；36，35，34 ；24，29。中间分裂了两次，与（2）（3）一致，就不详细画图了。

                                            

                      叶子节点的指针图方便我就没画了，大家自行脑补....

           （5）插入26。

                                           

                     此时第二个叶子节点需要进行分裂。

                                              

                    此时根节点的关键字个数也大于4，需要进行分裂。

                                       

          在网上找资料的时候，有看到一种说法，先判断要插入的叶子节点的关键字个数是否已达到D-1，若达到了则分裂，然后再进行插入操作。从原理上来说，先分裂再插入和先插入再分裂没有什么区别。但是在实现的时候，先分裂再插入会在分裂后额外的查找一次需要插入的叶子节点，会影响B树插入的效率。

          在实现B树时，可以将每个节点的数组容量设置为D，而不是D-1，这样可以容纳D个指针和D个关键字，方便在插入时的操作。

      删除：根据B树的定义4，B树节点中的关键字个数必须大于等于D/2-1(向上取整)（设该数值为S），所以在删除时需要对这个约束条件进行判断。

        1、要删除的关键字处于非叶子节点上：此时可以参考红黑树的删除，找到该关键字右子树的最左关键字（或左子树的最右关键字）替换到该关键字的位置，由此转换为删除叶子节点中的关键字的情况。

         2、要删除的关键字处于叶子节点上：

             （1）关键字删除后，该节点的关键字个数仍大于等于S：删除结束。

             （2）关键字删除后，该节点的关键字个数小于S：

                     ①该节点的兄弟节点关键字个数大于S：找兄弟节点“借”一个关键字，具体操作方式为：其父节点的关键字下移到该节点，其兄弟节点的关键字上移到父节点。

                     ②该节点的兄弟节点关键字个数刚好等于S：与其兄弟节点合并，具体操作方式为：其父节点的关键字下移，并将该节点与其兄弟节点合并。

         下面来看具体的例子：以上面插入时的B树为例：

        上图为情况②，若“34”“35”所在节点的兄弟节点有3个或以上的关键字时，则符合情况①，下面来举例说明：

                 

     tips：对于要删除关键字的叶子节点，可能即有左兄弟又有右兄弟，此时选择其中之一进行操作即可。

     总的来说，B树是为了磁盘等存储设备而设计出来的，有效的减少了磁盘IO次数，提升查找效率。但是在范围查询的方面仍有些“吃力”，而在数据库中范围查询是非常频繁的，所以由此引进了B树的变种---B+树。

B+树

     定义：B+树是B树的变种，其定义与B树基本相同，有以下不同及额外要求。

              1、有N棵子树的节点中，关键字也为N个（B树为N-1个）（即关键字个数为 [ D/2(向上取整), D ]）

              2、所有叶子节点中包含了全部的关键字信息，及指向这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接

              3、所有非叶子结点可以看成索引部分，节点中仅含有其子树中的最大（或最小）关键字

              下图为一颗三阶的B+树：

                                      

     插入：B+树的插入与B树的插入基本相同，不同之处在于：节点在分裂时，B+树中间的关键字不上移，而是将其的复制上移到父节点。

               例：在上图中插入25

                                     

                      分裂，并将25的复制上移（因为此树是属于节点中仅含有其子树中的最大关键字的情况）

                                    

                      分裂，并将25的复制上移

                                     

                      完毕

     删除：B+树的删除相比B树的删除简单很多，遇到需要合并节点的情况时，只需在合并后将其父节点对应的关键字索引删除即可。

 

       从Mysql（Inoodb）的角度来看，是使用B+树作为索引存储结构的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引，所以为了减少内存的占用，索引也会被存储在磁盘上。

       而B-树（B类树）的特定就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，当查询数据的时候，最好的情况就是很快找到目标索引，然后读取数据，使用B+树就能很好的完成这个目的，但是B-树的每个节点都有data域，这就会增大了节点大小，说白了增加了磁盘IO次数，而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。另外，B+树所有的Data域在叶子节点，并且所有的叶子节点都用指针串起来。这样遍历叶子节点就能获得全部数据，能极大的提升区间访问的效率。

目录：

一：静态查找表（Static Search Table）

主要操作：

二： 动态查找表（Dynamic Search Table）

主要操作：

三：顺序查找（Sequential Search）【线性查找】

1.查找过程

2.时间复杂度

四：折半查找（Binary Search）【二分查找】【有序表查找】

1.查找过程

2.时间复杂度

3.二分查找在静态查找表&动态查找表

A:静态查找表

B:动态查找表

五：插值查找（Interpolation Search）

1.查找过程

2.插值查找&二分查找的异同

A：同

B：异

六：斐波那契查找（Fibonacci Search）

1.查找过程

 2.时间复杂度

3.二分查找&插值查找&斐波那契查找的异同

A：同

B：异

七：索引顺序表查找【分块查找】

1.性能

2.查找过程

---

一：静态查找表（Static Search Table）

只作查找操作的查找表

 

主要操作：

（1）查询某个 ”特定的“ 数据元素是否在查找表中

（2）检索某个 ”特定的“ 数据元素和各种属性

静态查找表只是查询

1.顺序查找表【线性查找】：从线性表一端开始扫描，将扫到的关键字与给定值比较，相同则查找成功


2.有序表查找【折半查找】【二分查找】：若线性表有序，则可以折半查找
折半查找升级版为插值查找，及不取1/2处。斐波那契查找，也是折半查找的变种


3.索引顺序表查找【分块查找】：效率介于1）2）之间
又称分块查找。块与块之间有序，块内无序。实际进行两次查找，第一次折半查找，第二次顺序查找

 

 

二： 动态查找表（Dynamic Search Table）

在查找过程中同时插入查找表中不存在的数据元素

或者从查找表中删除已经存在的某个数据元素

 

主要操作：

（1）查找时插入数据元素

（2）查找时删除数据元素

动态查找表可以对查找表结构进行修改

相比于静态查找表，查找过程中会修改元素

 

 

三：顺序查找（Sequential Search）【线性查找】

也叫 线性查找

1.查找过程

是最基本的查找技术，它的查找过程是：

A:从表中第一个（或最后一个）记录开始

B:逐个进行记录的关键字和给定值比较

C:若某个记录的关键字等于给定值，则查找成功

D:如果直到最后一个（或第一个）记录，仍然找不到关键字与给定值相等的记录，则查找失败

2.时间复杂度

顺序查找的时间复杂度为

 

四：折半查找（Binary Search）【二分查找】【有序表查找】

又叫 二分查找

它的前提是线性表中的记录必须是关键码有序（通常从小到达有序），线性表必须采用顺序存储

1.查找过程

二分查找的基本思想是：

在有序表中

A:取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功

B:若给定值小于中间记录的关键字，则在中间记录的左半区继续查找

C:若给定值大于中间记录的关键字，则在中间记录的右半区继续查找

D:不断重复上述过程，直到查找成功

或所有查找区域无记录，查找失败为止

2.时间复杂度

二分查找的时间复杂度为

3.二分查找在静态查找表&动态查找表

由于 二分查找 的前提条件是要求集合有序

 

A:静态查找表

因此，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了

 

B:动态查找表

但对于需要频繁执行插入或删除操作的数据集（动态查找表）来说

维护有序的排序会带来不小的工作量，那就不建议使用

 

五：插值查找（Interpolation Search）

1.查找过程

根据要查找的关键字 key

与查找表中的最大最小记录的关键字比较后的查找方法

其核心在于插值计算公式：

2.插值查找&二分查找的异同

A：同

插值查找 与 二分查找 的时间复杂度都是

 

B:异

但对于表长较大，而关键字分布又比较均匀的查找表来说

插值查找算法的平均性能比二分查找要好的多

（因为，二分查找是折半查找

而插值查找会根据要查找的 key 计算得出其在整个查找表中的权重得到的位置会更接近 key 的位置）

反之，数组中如果分布类似

这种极端不均匀的数据

用插值查找未必是很合适的选择

 

六：斐波那契查找（Fibonacci Search）

1.查找过程

斐波那契查找与二分查找和插值查找都是有序查找算法

不过其是利用了黄金分割原理来实现的

其核心算法为：

A:当 时，查找成功

B:当时，新范围是第 low 个到第 mid-1 个，此时范围个数为个

C:当时，新范围是第 m+1 个到第 high 个，此时范围个数为 个

 2.时间复杂度

管斐波那契查找的时间复杂度也为 

3.二分查找&插值查找&斐波那契查找的异同

A:同

二分查找，插值查找 和 斐波那契查找 都是有序查找算法

它们的本质其实是相同的，都是选择序列中间的某个位置与给定值进行比较

依据序列的有序性，每次查找都可以去除两端一部分序列，从而提升查找性能

 

B：异

三者的区别仅在与中间位置的选择策略不同：

二分查找直接取序列中点作为 mid

插值查找按给定值在序列的权重（比例）作为 mid

斐波那契查找是用序列的黄金分割点（即：）作为 mid

但就平均性能来说，斐波那契查找要优于二分查找

还有一点比较关键的地方

二分查找是进行加减法与除法运算：

mid=low+(high-low)/2

插值查找进行复杂的四则运算：

mid=low+(high-low)*(key-a[low])/(a[high]-a[low])

斐波那契查找只是最简单的加减法运算：

mid=low+F[k-1]-1

在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率

 

七：索引顺序表查找【分块查找】

索引顺序查找，又称分块查找

 

是顺序查找的一种改进

1.性能

其性能介于顺序查找和折半查找之间

 

2.查找过程

A:分块查找把线性表分成若干块

每一块中的元素存储顺序是任意的

但是块与块之间必须是按关键字大小排序

（即前一块中的最大关键字大于（或小于）后一块中的最小（或最大）关键字值）。

B:另外，需要建立一个索引表

索引表中的一项对应线性表中的一项

索引表按关键字值递增（或递减）顺序排列

 

索引项由关键字域和链域组成

关键字域存放相应块的最大关键字

链域存放指向本块第一个结点的指针

 

索引表查找算法：实际上进行了两次查找（折半查找+顺序查找）

因此整个算法的平均查找长度是两次查找的平均查找长度之和