插值查找的思路与代码示例

插值查找跟折半查找一样，适用于有序表的查找。其实这两种查找方式的思路差不多，只不过插值查找不是折半，具体折多少是计算出来的，可能每次都不一样。打个比方，在英文词典里查“apple”，你下意识里翻开词典是翻前面的书页还是翻后面的书页？如果再让你查“zookeeper”呢？很显然，这里你肯定不是从中间查起，而是有一定目的的往前翻或往后翻。

对于折半查找，中间位置是：mid = (low + high) / 2
而插值查找位置是：pos = (key - arr[low]) / (arr[high] - arr[low]) * (high - low) + low

虽然插值查找的时间复杂度和折半查找相同，但对于表长较长，关键字又分布的比较均匀的查找表来说，插值查找的平均查找次数要少于折半查找。不过，插值查找的计算量要比折半查找大，这一点通过公式就能看出来。

public class InterpolationSearch {

    public static int search(int[] arr, int key) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int low = 0, high = arr.length - 1;
        if (key < arr[low] || key > arr[high]) // 不判断可能会出现数组角标越界
            return -1;
        //int pos = (key - arr[low]) / (arr[high] - arr[low]) * high;
        float x = key - arr[low];
        float y = arr[high] - arr[low];
        float z = high;
        int pos = (int) (x / y * z);
        
        //int count = 1;
        while (arr[pos] != key) {
            if (key > arr[pos])
                low = pos + 1;
            else
                high = pos - 1;

            if (high < low)
                return -1;
            //pos = (key - arr[low]) / (arr[high] - arr[low]) * (high - low) + low;
            x = key - arr[low];
            if (x < 0f)
                return -1;
            y = arr[high] - arr[low];
            z = high - low;
            pos = (int) (x / y * z + low);
            //count++;
        }
        //System.out.println("第" + count + "次查找找到了");
        return pos;
    }

    public static void main(String[] args) {
        testCase1();
    }

    public static void testCase() {
        int[] arr = {1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 16};
        for (int i = 0; i < arr.length; i++) {
            search(arr, arr[i]);
        }
    }

    public static void testCase1() {
        int[] arr = {1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 16};
        System.out.println(search(arr, 13));
    }

    public static void testCase2() {
        int[] arr = {1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 16};
        System.out.println(search(arr, 20));
    }

    public static void testCase3() {
        int[] arr = {1, 3, 4, 5, 6, 8, 9, 10, 11, 12, 16};
        System.out.println(search(arr, -1));
    }

    public static void testCase4() {
        int[] arr = {3};
        System.out.println(search(arr, 3));
    }
}