数据结构与算法-有序表查找(折半查找、插值查找、斐波那契查找)
程序员文章站
2022-07-12 09:48:11
...
引入
顺序查找虽然算法非常简单,对静态查找表的记录没有任何要求,但是当查找表记录数很大时,查找效率极为低下,所以只适用于小型数据的查找。
折半查找基本概念
折半查找(Binary Search)技术,又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败。
折半查找java代码实现
/**
* 折半查找
*
* @param a 查找表
* @param key 给定值
* @return 目标记录在查找表中的位置
*/
Integer binary_search(int[] a, int key) {
int low,high,mid;
low = 0; /* 定义最低下标为记录首位 */
high = a.length - 1; /* 定义最高下标为记录末位 */
while (low <= high) {
mid = (low + high) / 2; /* 折半 */
if (key < a[mid]) { /* 若查找值比中值小 */
high = mid - 1; /* 最高位调整到中位下标小一位 */
} else if (key > a[mid]) { /* 若查找值比中值大 */
low = mid + 1; /* 最低位调整到中位下标大一位 */
} else {
return mid; /* 若相等则说明mid即为查找到的位置 */
}
}
return null;
}
//声明查找表
int[] a = {1,2,3,4,5,6};
//测试调用
binary_search(a,2); //输出2
binary_search(a,22); //输出null
折半查找算法复杂度分析
- 如果将查找过程绘制成一棵二叉树,折半查找等于是把静态有序查找表分成了两棵子树,即查找结果只需要找其中的一半数据记录即可,等于工作量少了一半,然后继续折半查找,效率自然是非常高了。
- 尽管折半查找判断二叉树不是完全二叉树,但同样相同的推导可以得出,最坏的情况是查找到的关键字或查找失败的次数为log2n向下取整+1次,最好的情况是1次,因此最终我们折半算法的时间复杂度为0(logn),显然要远远好于顺序查找的O(n)。
折半查找改进版1:插值查找
- 折半查找的折半算法是:mid = (low + high) / 2 = low + (1 / 2) * (high - low)。
- 算法科学家考虑的就是将这个【1 / 2】进行改进:mid = low + ((key - a[low]) / (a[high] - a[low])) * (high - low)。
插值查找(Interpolation Search)是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式(key - a[low]) / (a[high] - a[low])。
应该说,从时间复杂度来看,它也是0(logn),但对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好得多。
反之,如果查找表中关键字分布得极不均匀,类似{0,1,2,···,400000,400001},那么插值查找未必是很合适的选择。
折半查找改进版2:斐波那契查找
- 折半查找是从中间分割,每一次查找总是一分为二,无论数据偏大还是偏小,很多时候这都未必是最合理的做法。除了插值查找,斐波那契查找(Fibonacci Search),利用黄金分割原理实现分割查找。
/**
* 斐波那契查找
*
* @param a 查找表
* @param key 给定值
* @return 目标记录在查找表中的位置
*/
Integer fibonacci_search(List<Integer> a, int key) {
/* 声明斐波那契数列(最大值大于【查找表记录数】即可) */
int[] f = {1,1,2,3,5,8,13,21};
int low, high, mid, k;
low = 0; /* 定义最低下标为记录首位 */
high = a.size() - 1; /* 定义最高下标为记录末位 */
k = 0;
while (a.size() - 1 > f[k] - 1) { /* 计算【查找表总记录数】位于斐波那契数列的位置 */
k++;
}
for (int i = a.size() - 1; i < f[k] - 1; i++) { /* 将不满的数值补全 */
a.set(i, a.get(a.size()-1));
}
while (low <= high) {
mid = low + f[k-1] - 1; /* 计算当前分割的下标 */
if (key < a.get(mid)) { /* 若查找记录小于当前分割记录 */
high = mid - 1; /* 最高下标调整到分割小标mid-1处 */
k = k - 1; /* 斐波那契数列下标减一位 */
} else if (key > a.get(mid)) { /* 若查找记录大于当前分割记录 */
low = mid + 1; /* 最低下标调整到分割小标mid+1处 */
k = k - 2; /* 斐波那契数列下标减两位 */
} else {
if (mid <= a.size() - 1) {
return mid; /* 若相等则说明mid即为查找到的位置 */
} else {
return a.size() - 1; /* 若mid>n,说明是补全数值,返回a.size()-1 */
}
}
}
return null;
}
- 斐波那契查找算法的核心在于:1) 当key=a[mid]时,查找成功;2) 当key<a[mid]时,新范围是第low个到第mid-1个,此时范围个数为f[k-1]-1个;3) 当key>a[mid]时,新范围是第mid+1个到第hign个,此时范围个数为f[k-2]-1个。
- 尽管斐波那契查找的时间复杂度也为0(logn),但就平均性能来说,斐波那契查找要优于折半查找。
总结
- 应该说,三种有序表的查找本质是分割点的选择不同,各有优势,实际开发时可根据数据的特点综合考虑再做出选择。