一.插值查找
插值查找通过下列公式
求取中点，其中low 和high 分别为表的两个端点下标，kx 为给定值。
若kx<tbl.elem[mid].key，则high=mid-1，继续左半区查找；
若kx>tbl.elem[mid].key，则low=mid+1，继续右半区查找；
若kx=tbl.elem[mid].key，查找成功。
插值查找是平均性能最好的查找方法，但只适合于关键码均匀分布的表，其时间效率依然是O(log2n)。
二.斐波那契查找
斐波那契查找通过斐波那契数列对有序表进行分割，查找区间的两个端点和中点都与斐波那契数有关。斐波那契数列定义如下：
设n 个数据元素的有序表，且n 正好是某个斐波那契数-1，即n=F(k)-1 时，可用此查找方法。
斐波那契查找分割的思想为：对于表长为F(i)-1 的有序表，以相对low 偏移量F(i-1)-1 取中点，即mid=low+F(i-1)-1，对表进行分割，则左子表表长为F(i-1)-1，右子表表长为F(i)-1-[F(i-1)-1]-1=F(i-2)-1。可见，两个子表表长也都是某个斐波那契数-1，因而，可以对子表继续分割。
【算法9.3】
① low=1；high=F(k)-1； // 设置初始区间
F=F(k)-1；f=F(k-1)-1； // F 为表长，f 为取中点的相对偏移量
② 当low>high 时，返回查找失败信息// 表空，查找失败
③ low≤high，mid=low+f; // 取中点
a. 若kx<tbl.elem[mid].key，则
p=f；f=F-f-1； // 计算取中点的相对偏移量
F=p； // 调整表长F
high=mid-1；转② // 查找在左半区进行
b. 若kx>tbl.elem[mid].key，则
F=F-f-1； // 调整表长F
f=f-F-1； // 计算取中点的相对偏移量
low=mid+1；转② // 查找在右半区进行
c. 若kx=tbl.elem[mid].key，返回数据元素在表中位置// 查找成功
当n 很大时，该查找方法称为黄金分割法，其平均性能比折半查找好，但其时间效率仍为O(log2n)，而且，在最坏情况下比折半查找差，优点是计算中点仅作加、减运算。
转载请注明：http://www.92nongye.com/xxmb/xxmb/23.html
