基本介紹插值查詢演算法類似於二分查詢，不同的是插值查詢每次從自適應的mid處開始查詢。二分查詢中求mid索引的公式轉成插值查詢mid索引公式，low表示左邊的索引，high表示右邊的索引，key表示要查詢的值程式碼案例

package com.xie.search;import java.util.ArrayList;import java.util.List;public class InsertValueSearch {    static int count = 0;    public static void main(String[] args) {        int[] arr = new int[102];        arr[0] = 1;        arr[1] = 1;        for (int i = 2; i < 102; i++) {            arr[i] = i;        }        List<Integer> indexList = insertValueSearch(arr, 0, arr.length - 1, 1);        System.out.println("indexList = " + indexList);        System.out.println("查詢次數：" + count);        /*        indexList = [1, 0]        查詢次數：1         */    }    /**     * 插值查詢，返回索引集合     *     * @param arr       陣列     * @param left      左邊索引     * @param right     右邊索引     * @param findValue 要查詢的值     * @return 找到就返回所有索引的集合，沒有就返回空     */    public static List<Integer> insertValueSearch(int[] arr, int left, int right, int findValue) {        count++;        List<Integer> indexList = new ArrayList<Integer>();        //注意：findValue < arr[0] || findValue > arr[arr.length - 1] 這個必須要，否則mid可能越界        if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {            return new ArrayList<Integer>();        }        int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);        int midValue = arr[mid];        if (findValue > midValue) {            return insertValueSearch(arr, mid + 1, right, findValue);        } else if (findValue < midValue) {            return insertValueSearch(arr, left, mid - 1, findValue);        } else {            //如果找到了，再向左掃描，將滿足條件的加入indexList            int temp = mid - 1;            while (true) {                if (temp < 0 || arr[temp] != findValue) {                    break;                }                indexList.add(temp);                temp--;            }            //再向右掃描,將滿足條件的加入indexList            temp = mid + 1;            while (true) {                if (temp > right || arr[temp] != findValue) {                    break;                }                indexList.add(temp);                temp++;            }            indexList.add(mid);            return indexList;        }    }}

注意事項對於資料量大，關鍵字分佈比較均勻的查詢表來說，採用插值查詢，速度較快。關鍵字分佈不均勻的情況下，該方法不一定比二分法要好。