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

不念不忘少年蓝@ 2022-04-10 03:58 379阅读 0赞

### 概要 ###

*   *   *  引入
         *  折半查找基本概念
         *  折半查找java代码实现
         *  折半查找算法复杂度分析
         *  折半查找改进版1：插值查找
         *  折半查找改进版2：斐波那契查找
         *  总结

### 引入 ###

> [顺序查找][Link 1]虽然算法非常简单，对静态查找表的记录没有任何要求，但是当查找表记录数很大时，查找效率极为低下，所以只适用于小型数据的查找。

### 折半查找基本概念 ###

> 折半查找（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)，显然要远远好于[顺序查找][Link 1]的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)，但就平均性能来说，斐波那契查找要优于折半查找。

### 总结 ###

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

[Link 1]: https://blog.csdn.net/FTD_SL/article/details/85233494