# 插值搜尋法(Interpolation Search)

插值搜尋法(Interpolation search)是假設資料呈線性相關分布，利用斜率公式來計算猜測搜尋鍵值的位置。搜尋方式與二分搜尋相同。

回想一下剛剛二元搜尋法，假設我們今天有一陣列如下，並且要搜尋 `1` ：

int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
List<Integer> resIndexList = binarySearch(arr, 0, arr.length - 1, 1);

使用二元搜尋法我們搜尋 `1` 需要調用 4 次，實際上這樣並不是很有效率，因為我們需要找到中間值再去找到 `1`。那麼，我們需要一種能夠快速定位到我們想要搜尋的值的方法，插值搜尋法可以實現我們想要達到的效果。

## 原理說明
1. 插值搜尋法其實和二元搜尋很類似，不一樣之處在於插值是每次從自訂的 mid 處開始搜尋。
2. 將折半搜尋中的求 mid 索引的公式，low 表示左邊索引，high表示右邊索引。
3. `int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);`

以下圖為例說明此公式是怎麼來的：

- left = x1 , right = x2
- arr[left] = arr[x1] , arr[right] = arr[x2]
- findVal = arr[m]


我們使用第三點的公式再回頭來算，我們需要幾次才能在這個陣列中搜尋到 `1` 呢？

int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
List<Integer> resIndexList = insertSearch(arr, 0, arr.length - 1, 1);

計算 mid：`int mid = 0 + (9 - 0) * (1 - 1) / (10 - 0) = 0`

直接就找到 1 在`arr[0]`。

假設要搜尋 `8`

計算 mid：`int mid = 0 + (9 - 0) * (8 - 1) / (10 - 0) = 6.3`

直接就找到 8 在`arr[7]`。 ***小數無條件進位**

也因此，插值很適合用在**數據量龐大**並且**陣列比較連續**的情況。

## 程式碼實現

基本上和二元搜尋法很像，不同之處在於二元搜尋法是一次砍半去找，而插值搜尋法是直接使用公式定位搜尋，程式碼的部分也僅有 mid 值不同而已，所以優化部分(陣列中含有多個相同值)直接參考二元搜尋法的即可。

package Search;

import java.util.Arrays;

public class InsertSearch {
    public static void main(String[] args) {
        int arr[] = new int[100];
        for(int i = 0; i < 100 ; i++) {
            arr[i] = i + 1;
        }

        System.out.println("原陣列: "+Arrays.toString(arr));

        int index = insertValueSearch(arr, 0, arr.length - 1, 55);
        System.out.println("55 在陣列中索引為: "+index);
    }
    /**
     * 插值搜尋要求陣列有序
     * @param arr 傳入的陣列
     * @param left 左邊索引
     * @param right 右邊索引
     * @param findVal 搜尋的值
     * @return 找到返回對應的索引, 否則返回 -1
     */
    public static int insertValueSearch(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 insertValueSearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) { // 向左遞迴
            return insertValueSearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

}

output

原陣列: [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, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 
56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
55 在陣列中索引為: 54

## 注意事項
1. 對於數據量較大，關鍵字分佈比較均勻的陣列來說，採用插值斯巡速度較快。
2. 關鍵字分佈不均勻的情況下，該方法不一定比二元搜尋法要好。