0%

查找-有序表查找(折半查找，插值查找，斐波拉契查找)

发表于 更新于 分类于

引言

如果待查找的数组是有序的，那么此时的查找就是有序表查找，这对于查找的帮助是很大的。属于有序表查找的有：折半查找（二分查找）、插值查找以及斐波那契查找。

1. 折半查找

折半查找又称为二分查找，是一种效率较高的查找算法。折半查找的先决条件是查找表中的数据元素排列必须是有序的。折半查找先以有序数列的中点位置为比较对象，如果要找的元素值小于中点位置元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，可以将查找的区间缩小一半，每次比较，都可以将当前查找范围缩小至一般，可以明显的减少比较的次数，提高查找效率。
时间复杂度：O(logn)
算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 定义接口
interface Searcher {
	/**
	 * 从数组array中查找关键字key,如果存在则返回该关键字在数组中任意出现的位置(不局限于首次或者末次之类的),否则返回-1
	 */
	int search(int[] array, int key);
}

/**
 * 二分法查找,时间复杂度O(logn)
 */
class BinarySearcher implements Searcher {
	// 二分法查找前提,查找表array是顺序(这里要求递增)排列的
	@Override
	public int search(int[] array, int key) {
		int low, high, mid;
		low = 0; // 定义最低下标为array首位
		high = array.length - 1; // 定义最高下标为array末位
		while (low <= high) {
			mid = (low + high) / 2; // 折半
			if (array[mid] > key) {
				// 中值比key大,则high=mid-1
				high = mid - 1;
			} else if (array[mid] < key) {
				// 中值比key小,则low=mid+1
				low = mid + 1;
			} else {
				// 相等说明mid即为key在array中所在位置
				return mid;
			}
		}
		return -1;
	}
}

2. 插值查找

插值查找是二分查找演化而来，相比于二分查找(折半),该算法考虑的是每次折的时候折多少,即不一定是1/2;如在一本字典中找”abstract”这个单词,我们自己来操作肯定是先翻到字典开始的那一小部分,而不是从字典的中间开始进行折半查找。

在二分查找中 mid = (low + high) / 2 = low + 1/2 * (high - low) ,插值查找就是对1/2(系数,或者说比例)进行改变，它将1/2变成 (key - array[low]) / (array[high] - array[low]),其实就是计算线性比例。

时间复杂度：O(logn)
因为插值查找是依赖线性比例的，如果当前数组分布不是均匀的，那么该算法就不合适。

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class InterpolateSearcher implements Searcher {

	@Override
	public int search(int[] array, int key) {
		int low, high, mid;
		low = 0; // 定义最低下标为array首位
		high = array.length - 1; // 定义最高下标为array末位
		while (low <= high) {
			// 相比二分法查找的更改处
			mid = low + (int) (1.0 * (key - array[low]) / (array[high] - array[low]) * (high - low));
			if (array[mid] > key) {
				// 中值比key大,则high=mid-1
				high = mid - 1;
			} else if (array[mid] < key) {
				// 中值比key小,则low=mid+1
				low = mid + 1;
			} else {
				// 相等说明mid即为key在array中所在位置
				return mid;
			}
		}
		return -1;
	}
}

3. 斐波那契查找

根据前面二分查找以及插值查找来看，有序表上的查找的关键就是如何分割当前查找的区域（二分查找对半分割，差值查找按线性比例分割），说到分割，还有一个著名的分割方式就是黄金分割。

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1) = 1，F(2) = 1，F(n) = f(n-1) + F(n-2) (n>=2)。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）

所以我们可以根据斐波那契数列对当前区域进行分割 :)

查找算法：在斐波那契数列找一个等于略大于查找表中元素个数的数F(n)，将原查找表扩展为长度为F(n)(如果要补充元素，则补充重复最后一个元素，直到满足数组元素个数为F(n)个元素)，完成后进行斐波那契分割，即F(n)个元素分割为前半部分F(n-1)个元素，后半部分F(n-2)个元素，找出要查找的元素在那一部分并递归，直到找到。
时间复杂度：O(logn)，平均性能优于二分查找。
算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class FibonacciSearcher implements Searcher {

	private static final int MAX_ARRAY_SIZE = 30;

	/**
	 * 得到长度为len的斐波那契数列
	 * 
	 * @return
	 */
	private int[] fibonacci(int len) {
		if (len < 0)
			throw new IllegalArgumentException("length must bigger than 0");
		int[] fibonacci = new int[len];
		fibonacci[0] = 1;
		fibonacci[1] = 1;
		for (int i = 2; i < len; i++) {
			fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
		}
		return fibonacci;
	}

	@Override
	public int search(int[] array, int key) {
		int low = 0; // 低位
		int len = array.length;
		int high = len - 1; // 高位
		int mid; // 中间位
		int k = 0; // 斐波那契数列下标(用于进行分割)
		// 获取斐波那契数列
		int[] fib = fibonacci(MAX_ARRAY_SIZE);
		// 获取斐波那契数列分割点位置
		while (len > fib[k] - 1) {
			k++;
		}
		// 创建临时数组(数组长度为fib[k] - 1)
		int[] tmp = new int[fib[k] - 1];
		// 拷贝原数组到tmp数组中
		System.arraycopy(array, 0, tmp, 0, len);
		// 填充tmp数组中剩余的位置,补充的元素值为最后一个元素值
		for (int i = len; i < fib[k] - 1; i++) {
			tmp[i] = array[high];
		}

		// 开始进行类似于二分查找的查找
		while (low <= high) {
			// 对于tmp数组,整个数组的长度为fib[k]-1
			// 而 fib[k]-1 = (fib[k-1]-1) + 1 + (fib[k-2]-1);
			// 所以可以这样理解： mid下标对应元素可以将整个数组拆分为两部分,第1部分有fib[k-1]-1个元素,第2部分有fib[k-2]-1个元素
			// mid=low+fib[k-1]-1; 正是将 数组的[low, max(high,tmp.length-1)]
			// 部分按照斐波那契规则分为两部分
			mid = low + fib[k - 1] - 1;
			if (tmp[mid] > key) {
				// 需要查找第1部分
				high = mid - 1;
				// fib[k] = fib[k-1] + fib[k-2]
				// 第一部分有fib[k-1]个元素,所以将k-1赋值为k
				k = k - 1;
			} else if (tmp[mid] < key) {
				// 需要查找第2部分
				low = mid + 1;
				// fib[k] = fib[k-1] + fib[k-2]
				// 第二部分有fib[k-2]个元素,所以将k-2赋值给k
				k = k - 2;
			} else {
				// 查找成功
				// 以下代码其实就是返回 min(mid, high);
				// return Math.min(mid, high);
				if (mid <= high)
					return mid;
				else
					return high; // 因为mid可能大于high,即查找到了补充的元素,那么还是应该返回high
			}
		}
		return -1;
	}
}

结束语

以上三种查找算法中，都依赖于顺序表，三者的区别本质上就是分割点选的不同。在分割点的选择中，折半查找 mid=(low+high)/2 是加法与除法运算；插值查找mid=low+(key-array[low])/(array[high]-array[low])*(high-low)是复杂的四则运算；斐波那契查找mid=low+fib[k-1]-1是简单的加减运算。在海量数据查找过程中细微的差别会影响最终的效率。

三种查找算法，各有优劣，实际开发可以根据数据的特点综合考虑再做出选择。