数据结构复习 (顺序查找,对半查找,斐波那契查找,插值查找,分块查找)

查找（检索）：

定义：从给定的数据中找到对应的K

1，顺序查找：

O(n)的从前向后的遍历

2，对半查找，要求有序

从中间开始查找，每次检查中间的是否正确，不正确就根据性质去左边or右边找

2.1对半插入排序

在找位置的时候是logn 去找， 但是最后需要换位置 排序之后仍然是O()N^2)

对同一序列分别进行对半插入排序和直接插入排序，两者之间

可能的不同之处是___D___。【考研题全国卷】

A.排序的总趟数

B.元素的移动次数

C.使用辅助空间的数量

D.元素的比较次数

2.2二叉判定树（扩充二叉树）：

在二叉树中空指针的位置，都增加特殊的结点（空叶结点），由此生成的二叉树称为扩充二叉树。称圆形结点为内结点，方

形结点为外结点

➢当high-low+1 £ 0时：T(low, high)为空；

➢当high-low+1 > 0时，令mid = ë(low+high)/2û

✓T(low, high)的根结点是mid ；

✓根结点的左子树是Rlow,…,Rmid-1对应的二叉判定树；

✓根结点的右子树是Rmid+1,…,Rhigh对应的二叉判定树。

对半查找算法的每次成功查找正好对应判定树的一个内结点，元素比较次数为该结点的深度加1，即从根到该结点所经过的结点数。

每次不成功的查找对应判定树的一个外结点，元素比较次数恰好为该结点深度，即根到该节点所经过的内结点数

平均失败的查找长度：外节点深度之和/外节点数（3.5）

平均成功查找长度：（内节点深度之和)/内节点数+1 （下面的是2.9）

➢优点：平均查找效率不超过O(logn) ，比顺序查找高。

➢缺点：

✓适用于有序数组，对有序链表难以进行二分查找。

✓适用于静态查找场景，若元素动态变化（频繁增删）后，

为了维持数组有序，需要O(n)时间调整，与顺序查找相比，

就没有优势了。

3,斐波那契查找

斐波那契数列：f0=0,f1=1;fi=fi-1+fi-2

斐波那契查找：
如果一个数组的长度是一个斐波那契数-1 ,那么他的左右就被分为了左边F(k-1)-1，中间一个，右边F(k-1)-；

所以我们可以尝试根据斐波那契数列来优化查找

假定数组中元素个数n是某个斐波那契数减1，即n=Fk-1。

令mid ¬ Fk-1把K与R[mid]比较，若：

➢K < R[mid]：在R[1]…R[Fk-1-1]内继续查找；

➢K > R[mid]：在R[Fk-1+1]…R[Fk-1]内继续查找；

➢K = R[mid]：则查找成功。

int FibSearch(int R[], int n, int K, int F[], int k){

int low=1,high=n;

while(low <= high){

int mid=low+F[k-1]-1;      //因为我们的F[k]=f[k-1]+f[k-2],现在以f[k-1]为mid

if(K<R[mid]) {high=mid-1; k--;}//我们抛弃了f[k-2] ,查找范围从low--low+f[k]--->low---low+f[k-1]

//长度为 f[k-1]-1

else if(K>R[mid]) {low=mid+1; k-=2;}  //我们抛弃了f[k-1],从low--f[k]--->low+f[k-1]-->low+f[k]

//长度为f[k-2]-1

else return mid;

}

return -1;

}

本质是从黄金比例查找

并且进入左边的几率更大,所需要的比较次数少,

4,插值查找

根据数学所学,根据直线算出可能的横坐标,假设原来的都是均分布且线性增长

平均时间复杂度:loglogn --->n

从O(logn)到O(loglogn)优势并不明显（除非查找表极长，

或比较操作成本极高）。

比如n=232 » 42.9亿

logn = log232 = 32

loglogn= log32 = 5

➢需引入乘除法运算。

➢元素分布不均匀时效率受影响。

➢实际中可行的方法：首先通过插值查找迅速将查找范围缩

小到一定的范围，然后再进行对半查找或顺序查找。

5,分块查找:

将大数组分成若干子数组（块），每个块中的数值都比后一块中数值小（块内不要求有序），建一个索引表记录每个子表的起始地址和各块中的最大关键字

查找的过程:先块间对半查找,再内部顺序查找,类似组相联cache