17 基本查找算法：插值查找與斐波那契查找

一商乎、插值查找

原理

在介紹插值查找之前，首先考慮一個新問題祭阀，為什么二分查找算法一定要是折半鹉戚，而不是折四分之一或者折更多呢？

打個比方专控，在英文字典里面查“apple”抹凳，你下意識翻開字典是翻前面的書頁還是后面的書頁呢？如果再讓你查“zoo”伦腐，你又怎么查赢底？
很顯然，這里你絕對不會是從中間開始查起柏蘑，而是有一定目的的往前或往后翻幸冻。

同樣的，比如要在取值范圍1 ~ 10000 之間 100 個元素從小到大均勻分布的數(shù)組中查找5咳焚，我們自然會考慮從數(shù)組下標較小的開始查找洽损。

經(jīng)過以上分析，折半查找這種查找方式黔攒，不是自適應的（也就是說是傻瓜式的）趁啸。二分查找中查找點計算如下：
mid=(low+high)/2, 即mid=low+1/2*(high-low);

通過類比，我們可以將查找的點改進為如下：
　　mid=low+(key-a[low])/(a[high]-a[low])*(high-low)督惰，

也就是將上述的比例參數(shù)1/2改進為自適應的不傅，根據(jù)關鍵字在整個有序表中所處的位置，讓mid值的變化更靠近關鍵字key赏胚，這樣也就間接地減少了比較次數(shù)访娶。

基本思想：

基于二分查找算法改進，將查找點的選擇改進為自適應選擇觉阅，可以提高查找效率崖疤。當然，差值查找也屬于有序查找典勇。

復雜度分析：

查找成功或者失敗的時間復雜度均為O(log2(log2n))劫哼。

注：對于表長較大，而關鍵字分布又比較均勻的查找表來說割笙，插值查找算法的平均性能比折半查找要好的多权烧。反之，數(shù)組中如果分布非常不均勻伤溉，那么插值查找未必是很合適的選擇般码。

Go語言描述

func InsertionSearch(arr []int, v, start, end int) int {
    if start <= end {
        mid := (v - arr[start]) / (arr[end] - arr[start]) * (end - start)
        // fmt.Println("mid:",mid)
        if arr[mid] == v {
            return mid
        } else if arr[mid] > v {
            // 左邊
            InsertionSearch(arr, v, start, mid-1)
        } else {
            // 右邊
            InsertionSearch(arr, v, mid+1, end)
        }
    }
    return -1
}

二、斐波那契查找

原理

上面我們講了插值查找乱顾，它是基于折半查找改進板祝，然后除了插值方式的切割外，還有基于斐波那契黃金分割點切割方式的改進走净。
我們先來了解一下斐波那契數(shù)列的特性：

|--------------- F(K)-1 ---------------|
|_______________________|_______________|
|------- F(K-1)-1 -----|--- F(K-2)-1 --|
斐波那契數(shù)列券时，又稱黃金分割數(shù)列，之所以它又稱為黃金分割數(shù)列伏伯，是因為它的前一項與后一項的比值隨著數(shù)字數(shù)量的增多逐漸逼近黃金分割比值0.618革为。
所以斐波那契查找改變了二分查找中原有的中值 mid 的求解方式，其 mid 不再代表中值舵鳞，而是代表了黃金分割點：
mid = left + F_{block - 1} - 1

基本思想：

假設表中有 n 個元素震檩，查找過程為取區(qū)間中間元素的下標 mid ，對 mid 的關鍵字與給定值的關鍵字比較：
（1）如果與給定關鍵字相同蜓堕，則查找成功抛虏，返回在表中的位置；
（2）如果給定關鍵字大套才，向右查找并減小2個斐波那契區(qū)間迂猴；
（3）如果給定關鍵字小，向左查找并減小1個斐波那契區(qū)間背伴；
（4）重復過程沸毁，直到找到關鍵字（成功）或區(qū)間為空集（失敺逅琛）。

復雜度分析：

最壞情況下息尺，時間復雜度為O(lgN)携兵，且其期望復雜度也為O(lgN)。

Go語言描述

func FibonacciSearch(arr []int, v int) int {
    fibs := getFibonacciArray(10)
    fmt.Println("fibonacciArray:", fibs)

    // 根據(jù)斐波那契數(shù)列找適合的區(qū)間
    k := 0
    l := len(arr)
    for l > fibs[k] {
        k++
    }

    // 2搂誉、構建新序列徐紧，多出位補slice[n-1]
    tmpArr := make([]int, fibs[k]-1)
    copy(tmpArr, arr)
    for i := l; i < len(tmpArr); i++ {
        tmpArr[i] = arr[l-1]
    }

    // 開始斐波那契查找
    left, right := 0, l-1
    for left <= right {
        // 找黃金分割點
        mid := left + fibs[k-1] - 1
        // fmt.Println("mid:", mid)
        // fmt.Println("tmpArr:", tmpArr)

        if tmpArr[mid] == v {
            if mid < l {
                return mid
            } else {
                // 位于tempS的填補位
                return l - 1
            }
        } else if tmpArr[mid] > v {
            // 左邊
            right = mid - 1
            // 查找值在前面的fibs(k-1)區(qū)間中
            k -= 1
        } else {
            // 右邊
            left = mid + 1
            // 查找值在后面的fibs(k-2)區(qū)間中
            k -= 2
        }
    }
    return -1
}

// 獲取斐波那契數(shù)列
func getFibonacciArray(n int) []int {
    fArr := make([]int, n+1, n+1) // 數(shù)列第一位從下標1開始

    fArr[1] = 1
    fArr[2] = 1

    for i := 3; i <= n; i++ {
        fArr[i] = fArr[i-1] + fArr[i-2]
    }

    return fArr[1:]
}

小結

折半查找：以一半元素來分割數(shù)組；
插值查找：根據(jù)關鍵字在整個有序表中所處的位置炭懊，讓mid值的變化更靠近關鍵字key;
斐波那契查找：以斐波那契數(shù)列元素之間的黃金分割點來分割數(shù)組并级。