欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法-有序表查找(折半查找、插值查找、斐波那契查找)

程序员文章站 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),但就平均性能来说,斐波那契查找要优于折半查找。

总结

  • 应该说,三种有序表的查找本质是分割点的选择不同,各有优势,实际开发时可根据数据的特点综合考虑再做出选择。

上一篇: ROS之topic

下一篇: 54. 螺旋矩阵