1. 差值查找算法

1.1 插值查找原理介绍

  1. 插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。
  2. 将折半查找中的求 mid 索引的公式 , low 表示左边索引 left, high 表示右边索引 right.
    key 就是前面我们讲的 findVal
  4. 对应前面的代码公式：int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

1.2 举例说明插值查找算法

1.3 代码实现

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
public class InsertValueSearch {

	public static void main(String[] args) {
		
		//得到测试数组
		int[] arr = new int[100];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = i + 1;
		}
		
	 	int indexResult = insertValueSearch(arr, 0, arr.length-1, 36);
		System.out.println("index = "+ indexResult);
		
	}
	
	
	/**
	 * 插入查找的方法
	 * int mid = left + (searchVal - arr[left])*(right-left)/(arr[right]-arr[left]);
	 */
	public static int insertValueSearch(int[] arr,int left,int right,int searchVal) {
		
		//searchVal < arr[0] 和 searchVal > arr[arr.length-1] 必须有，否则我们得到的mid可能越界
		if(left > right || searchVal < arr[0] || searchVal > arr[arr.length-1]) {
			return -1;
		}
		
		System.out.println("ssss");
		int mid = left + (searchVal - arr[left])*(right-left)/(arr[right]-arr[left]);
		
		if(searchVal < arr[mid]) {
			return insertValueSearch(arr, left, mid-1, searchVal);
		}else if(searchVal > arr[mid]) {
			return insertValueSearch(arr, mid+1, right, searchVal);
		}else {
			return mid;
		}
		
	}

}

1.4 插值查找注意事项

  1. 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快。
  2. 关键字分布不均匀的情况下，该方法不一定比折半查找要好。