【原】203，查找-插值查找

二分法查然效率很高，但我们为什么要和中间的值进行比较，如果我们和数组1/4或者3/4部分的值进行比较可不可以呢，对于一个要查找的数我们不知道他大概在数组的什么位置的时候我们可以使用二分法进行查找。但如果我们知道要查找的值大概在数组的最前面或最后面的时候使用二分法查找显然是不明智的。比如我们查字典的时候如果是a或者b开头的我们一般会在前面找，如果是y或者z开头的我们一般偏向于往后面找，这个时候如果我们使用二分法从中间开始找显然是不合适的。之前二分法查找的时候我们比较的是中间值，mid=low+1/2*(high-low);但插值查找的时候我们比较的不是中间值，是mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，我们来看下插值查找的代码。

 1public static int insertSearch(int[] array, int key) {
 2    return search(array, key, 0, array.length - 1);
 3}
 4
 5private static int search(int[] array, int key, int left, int right) {
 6    while (left <= right) {
 7        if (array[right] == array[left]) {
 8            if (array[right] == key)
 9                return right;
10            else return -1;
11        }
12        int middle = left + ((key - array[left]) / (array[right] - array[left])) * (right - left);
13        if (array[middle] == key) {
14            return middle;
15        }
16        if (key < array[middle]) {
17            right = middle - 1;
18        } else {
19            left = middle + 1;
20        }
21    }
22    return -1;
23}

他和二分法查找代码很相似，只不过计算middle的方式不一样。再来看一下递归的版本

 1public static int insertSearch(int[] array, int key) {
 2    return search2(array, key, 0, array.length - 1);
 3}
 4
 5private static int search2(int array[], int key, int left, int right) {
 6    if (left > right)
 7        return -1;
 8    if (array[right] == array[left]) {
 9        if (array[right] == key)
10            return right;
11        else return -1;
12    }
13    int mid = left + (key - array[left]) / (array[right] - array[left]) * (right - left);
14    if (array[mid] == key)
15        return mid;
16    if (array[mid] > key)
17        return search2(array, key, left, mid - 1);
18    return search2(array, key, mid + 1, right);
19}