大话数据结构-查找-有序表查找

注：本文同步发布于稀土掘金。

3 有序表查找

3.1 折半查找

  折半查找（Binary Search）技术，又称为二分查找，它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。

  折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

  代码有多种实现方式，以下是示例：

/*** Binary Search** @author Korbin* @date 2023-04-19 17:57:03**/
public class BinarySearch<T extends Comparable<T>> {/*** binary search* <p>* return index in data if searched, else return -1** @param data array to search* @param key  key to search* @return index of key in data* @author Korbin* @date 2023-04-19 18:30:33**/public int binarySearch(T[] data, T key) {int length = data.length;int from = 0;int to = length - 1;// if key little than data[0] or key greater than data[length - 1], return -1, means search failedif (data[from].compareTo(key) > 0 || data[to].compareTo(key) < 0) {return -1;}int mid = ((to - from) + 1) / 2;while (from < to) {// if data[mid] equals key, then return midif (data[mid].equals(key)) {return mid;}if (data[mid].compareTo(key) < 0) {// if key greater than data[mid], then search from [mid + 1, to]from = Math.min(mid + 1, length - 1);} else if (data[mid].compareTo(key) > 0) {// if key little than data[mid], then search from [from, mid - 1]to = Math.max(mid - 1, 0);}if (from == to) {// if from equals to, then check if data[from] equals keyreturn (data[from].equals(key)) ? from : -1;}mid = from + ((to - from) + 1) / 2;}return -1;}}

3.2 插值查找

  插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心在于插值公式$\frac{key-a[from]}{a[to]-a[flow]}$。

  从时间复杂度来看，它也是O(logn)，但对于表长较大，而关键字又分布比较均匀的查找表来说，插值查找的平均性能要比折半查找算法的性能要好很多。反之，如果数组分布不均匀，用插值查找未必有优势。

  插值查找是在折半查找的基础上进行优化的，在折半查找中，计算mid的算法为：

  $mid=from+\frac{1}{2}((to-from)+1)$

  在插值查找算法中，则是：

  $mid=from+\frac{key-a[from]}{a[to]-a[flow]}((to-from)+1)$

  因此代码只作少量改动：

/*** interpolation search* <p>* return index in data if searched, else return -1** @param data array to search* @param key  key to search* @return index of key in data* @author Korbin* @date 2023-04-19 18:30:33**/
public int interpolationSearch(int[] data, int key) {int length = data.length;int from = 0;int to = length - 1;// if key little than data[0] or key greater than data[length - 1], return -1, means search failedif (data[from] > key || data[to] < key) {return -1;}int mid = ((key - data[from]) / (data[to] - data[from])) / 2 * ((to - from) + 1);while (from < to) {// if data[mid] equals key, then return midif (data[mid] == key) {return mid;}if (data[mid] < key) {// if key greater than data[mid], then search from [mid + 1, to]from = Math.min(mid + 1, length - 1);} else if (data[mid] > key) {// if key little than data[mid], then search from [from, mid - 1]to = Math.max(mid - 1, 0);}if (from == to) {// if from equals to, then check if data[from] equals keyreturn (data[from] == key) ? from : -1;}mid = from + ((key - data[from]) / (data[to] - data[from])) / 2 * ((to - from) + 1);}return -1;
}

  调整一下mid的计算方式即可。

3.3 斐波那契查找

  以下是一个斐波那契数组：

  斐波那契数组的特性是，后一个元素的值等于前两个元素值的和，即F[K]=F[K-1]+F[K-2]。此外，F[K]/F[K+1]无限接近于0.618。斐波那契查找法依据这一特性，将数据分割成两部分，并把F[K-1]-1作为mid值进行对比处理。

  例如，假设数组长度是8，8在斐波那契数组中的下标是6，那么把数组分为两段，长度分别是F[K-1]=F[5]=5，F[K-2]=F[4]=3，令mid=F[K-1]-1=5-1=4，比较要查找的数值与被查找的数组A中，下标为4的元素的大小。

  在持续查找的过程中，被查找的数组A因为是有序数组，所以如果mid所对应的元素值大于要查找的数值时，进行下一轮查找时，则应到被查找数组的下半段去查找，下半段数组长度是多少呢？上文提到，裴波那契数组的特性F[K]=F[K-1]+F[K-2]，而斐波那契查找就是将数组分成两段，前半段长度是F[K-2]，后半段长度是F[K-1]，因此当我们在后半段查找时，后半段的数组长度是F[K-1]，即新的K=K-1，接下来的mid计算方式仍然不变。

  而这种情况下，下标为mid以及其后的元素，在下一轮查找时显然不可以再用于查找，因此它们肯定会大于要查找的这个值，因此我们设置一个变量high，令其初始值为数组的长度，在A[mid]大于要查找的数值时，令high=mid-1，表示最多可以被查找的元素下标是high，对应的元素值是A[high]。

  而如果mid所对应的元素值小于要查找的数值时，需要进行下一轮查找时，因为前半段长度为F[K-2]，因此新的K=K-2，而mid的计算方式不再是mid=F[K-1]-1，而是“上一轮的mid”+1+F[K-1]-1，我们设置一个变更low，令其等于“上一轮的mid”+1，那么，mid的计算方式就变成了mid=low+F[K-1]-1，由于第一轮查找时没有“上一轮的mid”，所以如果按照这个公式，第一轮的low则为1，这样可以保证mid的计算公式一直是mid=low+F[K-1]-1。

  根据以上分析，可知：

  (1) 变量mid，表示使用数组中下标为mid的元素与要查找的数值进行比较；

  (2) 变量k，表示被查找的数组长度在斐波那契数组中的位置；

  (3) 变量low，表示从数组的下标为low的元素开始查找，初始值为1，当A[mid]<被查找的元素时，low=mid+1，同时置k=k-2；

  (4) 变量high，表示最多查到数组的下标为high的元素，初始值为数组的最大下标，当A[mid]>被查找的元素时，high=mid-1，同时置k=k-1；

  现在我们来开始尝试，假设有以下数组：

  我们需要从中找到数值59所在的位置。

  首先，初始化，low=1，high=数组的最大下标=10，同时定义一个斐波那契数组：

  然后第一次查找，我们来找k，已知数组长度为11，在斐波那契数组f中并未找到10这个元素，有两个选择：

  如果选择8，即k=6，f[k]=f[6]=8，假设我们要查找的是99，会出现什么情况呢：

  (1) 第一轮，mid=low+f[k-1]-1=1+f[5]-1=1+5-1=5，由于a[mid]<要查找的数值，因此新的k=k-2=3，新的low=mid+1=5+1=6；

  (2) 第二轮，mid=low+f[k-1]-1=6+f[2]-1=6+1-1=6，由于a[mid]<要查找的数值，因此，新的k=k-2=0，新的low=mid+1=6+1=7；

  (3) 第三轮，mid=low+f[k-1]-1=7+f[0-1]-1，无法再继续，而此时仍有a[7]~a[10]；

  如果选择13，即k=7，f[k]=f[7]=13，假设我们要查找的是99，会出现什么情况呢：

  (1) 第一轮，mid=low+f[k-1]-1=1+f[6]-1=1+8-1=8，a[8]<99，因此新的k=k-2=4，新的low=mid+1=8+1=9；

  (2) 第二轮，mid=low+f[k-1]-1=9+f[3]-1=9+3-1=11，这时会发现，11已经超过了a的最大下标10，查找直接失败；

  (3) 此时我们进行一些调整，将数组a的长度扩大到f[k]即13位，并补齐后两位的值为f[10]，即f[11]=f[12]=f[10]=99，这时再来查询，就可以得到a[11]=99，找到99在数组a的下标为11的位置，而由于原始的a最大下标为10，因此直接返回10即可。

  由此找到规则：当数组长度在斐波那契数组中找不到对应元素时，取与数组长度相邻，但大于数组长度的那个元素的下标作为k，同时将被查找的数组长度扩大到k，并补齐后续元素值使其等于被查找的数组的最后一个元素值。

  因此我们取k=7，此时数组a和f的结构如下所示：

  开始第一轮查找，此时mid=low+f[k-1]-1=1+f[6]-1=1+8-1=8，a[8]=73>59，因此high=mid-1=8-1=7，k=k-1=7-6=6：

  第二轮查找，mid=low+f[k-1]-1=1+f[5]-1=5，a[5]=47<59，因此low=mid+1=5+1=6，k=k-2=6-2=4：

  第三轮查找，mid=low+f[k-1]-1=6+f[2]-1=6+1-1=6，a[6]=59，得到查找结果，返回查找值59所在的下标是6，查找结束。

  依据以上分析，代码实现比较简单：

import java.util.Arrays;/*** 斐波那契查找** @author Korbin* @date 2023-11-09 09:16:33**/
public class FibonacciSearch {/*** 定义一个斐波那契数组** @param length 数组长度* @return 斐波那契数组* @author Korbin* @date 2023-11-09 09:26:32**/private static int[] fibonacciArray(int length) {int[] array = new int[length];array[0] = 0;if (length == 1) {return array;} else if (length == 2) {array[1] = 1;return array;} else {array[1] = 1;for (int i = 2; i < length; i++) {array[i] = array[i - 1] + array[i - 2];}return array;}}/*** 查找key在数组array中的下标，找不到时返回-1** @param array 被查找的数组* @param key   要查找的key* @return key在array中的下标* @author Korbin* @date 2023-11-09 09:28:51**/private static int fibonacciSearch(int[] array, int key) {int length = array.length;// 如果被查找的数组只有一位，则直接比较返回if (length == 1) {if (array[0] == key) {return 0;} else {return -1;}}// 因为是从下标为1的数组开始查找的，因此先比较下标为0的元素if (array[0] == key) {return 0;}int[] fibonacciArray = fibonacciArray(length);// low初始为1int low = 1;// high初始为length - 1int high = length - 1;// 从斐波那契数组中找到kint k = 0;for (int i = 0; i < length; i++) {if (length > fibonacciArray[i]) {k++;}}// 如果被查找的数组长度小于k，则扩充数组int[] newArray = Arrays.copyOf(array, fibonacciArray[k]);if (fibonacciArray[k] > length) {for (int i = length; i < fibonacciArray[k]; i++) {newArray[i] = array[length - 1];}}// 开始查找while (low <= high) {// 计算midint mid = low + fibonacciArray[k - 1] - 1;if (key < newArray[mid]) {high = mid - 1;k = k - 1;} else if (key > newArray[mid]) {low = mid + 1;k = k - 2;} else {if (mid < length) {return mid;} else {return length - 1;}}}return -1;}public static void main(String[] args) {int[] array = new int[]{0, 1, 16, 24, 35, 47, 59, 62, 73, 87, 99};for (int j : array) {int index = fibonacciSearch(array, j);System.out.println("元素" + j + "的下标是" + index);}}}