和二分法一样，插值查找算法也可以在有序序列中查找某个数值，一般情况下插值查找算法的速度比二分法要快的多，能有效减少查找循环的次数，属于二分查找法的优化。使用插值查找算法的前提是待查找的序列必须是有序的，如果不是可以先转换为有序序列后再进行查找。

1、插值查找算法介绍

用途：能在大量的数据中找到自己想找的元素，减少查找的循环的次数。

条件：插值查找算法类似于二分查找法，必须是有序列表。对于非有序序列，可以先进行排序后再使用插值查找算法查找。

原理：对一个有序数列进行查找的时候，二分法（即折半查找）是利用中间值middle来一步步缩小搜索的范围，直至找到最终结果。时间复杂度：O(log(n))。插值查找算法同二分法类似，唯独中间值middle的计算方式不一样，该middle值会尽可能的接近我们要查找的值，减少查找的次数，时间复杂度一样为 O(log(n))。

对于数据量较大，关键字分布比较均匀的有序表来说，采用插值查找算法, 速度较快。
对于关键字分布不均匀的情况，插值查找算法不一定比二分查找算法(折半查找算法)要好。

求middle索引(即获取数组中间的索引)公式：

二分查找(即折半查找): int middle = (left+right)/2
插值查找: int middle = low + (high - low) * (findVal - arr[low]) / (arr[high] - arr[low]) 。

假设a[10]={1,16,24,35,47,59,62,73,88,99}，low=0，high=9，则a[low]=1，a[high]=99，如果我们要找的是key=16时，按原来折半的做法，我们需要四次才可以得到结果，但如果用插值算法，计算(key-a[low])/(a[high]-a[low])=(16-1)/(99-1)≈0.153，即mid≈0+0.153×(9-0)=1.377，取整得到mid=1，我们只需要一次就查找到结果了，显然大大提高了查找的效率。

这就是插值查找和二分查找的不同之处，插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式(key-a[low])/(a[high]-a[low])。从时间复杂度来看，它也是O(logn)，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。反之，由于插值的计算依赖于最大值和最小值，因此数组中如果分布类似{0,1,2,2000,2001,…,999998,999999}这种极端不均匀的数据，用插值查找效率比二分查找低。因此插值查找应用有限。

插值查找算法使用方法：

将长度为n的数组进行排序，升降序都可以。
先把数组的范围标记好，分别用low和high来表示数组的范围，然后找到数组的中间元素 int middle = low + (high - low) * (findVal - arr[low]) / (arr[high] - arr[low]) 。
使用 middle 位置的元素和所查找的元素 findVal 进行对比，如果 findVal 的数值较为大的话，就进入（mid，high）的范围在进行查找元素，如果 key 的元素较为小的话就进入（low，mid）的范围查找。
循环这个步骤，这时我们只需要根据 findVal，与数组的最中间的值进行比较，根据结果改变low，high的值就好了。直到找到对应的值或者区间缩小到左右端点之间不再包含其他数据结束。

2、问题及实现方式

2.1 问题

有一个无重复数字的数组中，利用插值算法查找某个数字在数组中的位置，找到则返回其位置索引，没找到返回-1.

2.2 实现方式

2.2.1 递归算法

import java.util.Arrays;

/**
 * 插值查找
 * <p>
 * 思想：
 * 就是将二分法的mid=（left+right）/2，
 * 变成mid=left+(right-left)*()(findVal-arr[left])/(arr[right]-arr[left]))
 * 然后递归
 */
public class InsertSearch {
    public static void main(String[] args) {
        int array[] = {11, 23, 54, 65, 76, 13, 55, 66, 70, 98, 30, 99, 103};
        // 将数组排序
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
        /* 查找元素65的位置(递归算法) */
        System.out.println(insertSearch(array, 0, array.length - 1, 65));
    }

    /**
     * 插值查找-递归算法
     *
     * @param arr     数组
     * @param left    左索引
     * @param right   右索引
     * @param findVal 要查找的值
     * @return
     */
    public static int insertSearch(int[] arr, int left, int right, int findVal) {
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return -1;
        }
        int mid = left + (right - left) * ((findVal - arr[left]) / (arr[right] - arr[left]));
        int midVal = arr[mid];
        if (findVal > midVal) {
            return insertSearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            return insertSearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

}

2.2.2 非递归算法（循环）

package com.kz.example.algorithm.find;

import java.util.Arrays;

/**
 * 插值查找
 * <p>
 * 思想：
 * 就是将二分法的mid=（left+right）/2，
 * 变成mid=left+(right-left)*()(findVal-arr[left])/(arr[right]-arr[left]))
 * 然后递归
 */
public class InsertSearch {
    public static void main(String[] args) {
        int array[] = {11, 23, 54, 65, 76, 13, 55, 66, 70, 98, 30, 99, 103};
        // 将数组排序
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));
        /* 查找元素65的位置(非递归算法) */
        System.out.println(insertSearch(array, 65));
    }

    /**
     * 插值查找-非递归算法
     *
     * @param arr     数组
     * @param findVal 要查找的值
     * @return
     */
    public static int insertSearch(int arr[], int findVal) {
        if (findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) * ((findVal - arr[left]) / (arr[right] - arr[left]));
            if (arr[mid] == findVal) {
                return mid;
            }
            if (arr[mid] > findVal) {
                right = mid - 1;
            }
            if (arr[mid] < findVal) {
                left = mid + 1;
            }
        }
        return -1;
    }
}

3、插值算法和二分法的性能比较

import java.util.ArrayList;
import java.util.List;

/**
 * 插值查找和二分法查找的比较
 * <p>
 * 二分法的 mid=（left+right）/2，
 * 插值的 mid=left+(right-left)*()(findVal-arr[left])/(arr[right]-arr[left]))
 */
public class InsertAndBinarySearch {
    public static void main(String[] args) {
        //生成一个1到100的有序数组
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
        List<Integer> indexList1 = insertSearch(arr, 0, arr.length - 1, 1, 0);
        System.out.println("插值查找---需要查找的数值为1的索引=" + indexList1.get(0) + ", 查找次数 = " + indexList1.get(1));
        List<Integer> indexList11 = binarySearch(arr, 0, arr.length - 1, 1, 0);
        System.out.println("二分法查找---需要查找的数值为1的索引=" + indexList11.get(0) + ", 查找次数 = " + indexList11.get(1));
        System.out.println("================================");
        List<Integer> indexList2 = insertSearch(arr, 0, arr.length - 1, 50, 0);
        System.out.println("插值查找---需要查找的数值为50的索引=" + indexList2.get(0) + ", 查找次数 = " + indexList2.get(1));
        List<Integer> indexList22 = binarySearch(arr, 0, arr.length - 1, 50, 0);
        System.out.println("二分法查找---需要查找的数值为50的索引=" + indexList22.get(0) + ", 查找次数 = " + indexList22.get(1));
        System.out.println("----------------------------");
        List<Integer> indexList3 = insertSearch(arr, 0, arr.length - 1, 100, 0);
        System.out.println("插值查找---需要查找的数值为100的索引=" + indexList3.get(0) + ", 查找次数 = " + indexList3.get(1));
        List<Integer> indexList33 = binarySearch(arr, 0, arr.length - 1, 100, 0);
        System.out.println("二分法查找---需要查找的数值为100的索引=" + indexList33.get(0) + ", 查找次数 = " + indexList33.get(1));
    }

    /**
     * 插值查找-递归算法
     *
     * @param arr     数组
     * @param left    左索引
     * @param right   右索引
     * @param findVal 要查找的值
     * @param times   查找的次数
     * @return
     */
    public static List<Integer> insertSearch(int[] arr, int left, int right, int findVal, int times) {
        times++;
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            List<Integer> list = new ArrayList<>();
            // 第一个值为查找的索引位置
            list.add(-1);
            // 第二个值为查找的次数
            list.add(times);
            return list;
        }
        int mid = left + (right - left) * ((findVal - arr[left]) / (arr[right] - arr[left]));
        int midVal = arr[mid];
        if (findVal > midVal) {
            return insertSearch(arr, mid + 1, right, findVal, times);
        } else if (findVal < midVal) {
            return insertSearch(arr, left, mid - 1, findVal, times);
        } else {
            List<Integer> list = new ArrayList<>();
            // 第一个值为查找的索引位置
            list.add(mid);
            // 第二个值为查找的次数
            list.add(times);
            return list;
        }
    }

    /**
     * 二分法查找元素的位置 递归算法，需要传递数组的头和尾的位置。
     *
     * @param array 数组
     * @param value 需要查找的值
     * @param low   查找的头部位置
     * @param high  查找的尾部位置
     * @param times 查找的次数
     * @return
     */
    public static List<Integer> binarySearch(int array[], int low, int high, int value, int times) {
        times++;
        int mid;
        mid = (low + high) / 2;
        if (low > high) {
            List<Integer> list = new ArrayList<>();
            // 第一个值为查找的索引位置
            list.add(-1);
            // 第二个值为查找的次数
            list.add(times);
            return list;
        }
        if (array[mid] == value) {
            List<Integer> list = new ArrayList<>();
            // 第一个值为查找的索引位置
            list.add(mid);
            // 第二个值为查找的次数
            list.add(times);
            return list;
        } else if (array[mid] > value) {
            return binarySearch(array, low, mid - 1, value, times);
        } else {
            return binarySearch(array, mid + 1, high, value, times);
    }

}

有上述结果可以看出，查找中间值时二分法要快的多，而靠近两端的数值使用插值查找算法要快。

目录CONTENT

使用插值查找算法在有序序列（数组）中查找元素的位置