參考資料：
http://www.cnblogs.com/yw09041432/p/5908444.html
https://my.oschina.net/u/140462/blog/282319

插值與斐波那契查找都是基于2分查找的；

插值查找##

當(dāng)翻字典找單詞，比如“better”時，我們絕逼不是從字典中間開始找，而是，相對靠前找吧，這就是按照一定的比例來進(jìn)行分割查找的過程；
折半查找，我們計算mid的方式是：
mid = (low + high) / 2， 也就是 low + 1/2 * (high - low) ;
插值將其改進(jìn)成：
mid = low + (key-a[low]/a[high]-a[low])*(high-low);
也就是將上述的比例參數(shù)1/2改進(jìn)為自適應(yīng)的，根據(jù)關(guān)鍵字在整個有序表中所處的位置，讓mid值的變化更靠近關(guān)鍵字key，這樣也就間接地減少了比較次數(shù)。

注意
對于表長較大，而關(guān)鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數(shù)組中如果分布非常不均勻，那么插值查找不一定合適了。

特別注意： 插值中的*1.0f，避免計算機整除；

int insert_search(int a[], int key, int n) {
    int low = 0;
    int high = n-1;
    int index = -1;
    int time = 0;
    
    
    while(low <= high) {
        // 因計算機整除問題，需要在分母上需加入0.5
        mid = low + (key-a[low])/((a[high]-a[low]) * 1.0)*(high-low);
        printf("查找次數(shù)：%d, 當(dāng)前mid：%d\n", ++time, mid);
        
        if(a[mid] == key) {
            index = mid;
            break;
        } else if(a[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return index;
}

int half_search(int array[], int key, int n) {
    int low = 0;
    int high = n-1;
    int index = -1;
    int time = 0;
    
    
    while(low <= high) {
        int mid = (low + high) / 2;
        printf("查找次數(shù)：%d, 當(dāng)前mid：%d\n", ++time, mid);
        
        if(array[mid] == key) {
            index = mid;
            break;
        } else if(array[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    return index;
}

// 插值查找
int main(int argc, const char * argv[]) {
    int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24};
    
    //int a[] = {1,19,88,109,200,230,270,299,900,1000,1001,5000,5010,5400,5900,7000,8000,8099,9012,9099,9999,10002,12093,15432};

    int value = 23;
    printf("插值查找\n");
    int index = insert_search(a, value, 24);
    if(index > -1) {
        printf("找到了，下標(biāo)是：%d\n", index);
    }
    
    printf("折半查找\n");
    
    int index2 = half_search(a, value, 24);
    if(index2 > -1) {
        printf("找到了，下標(biāo)是：%d\n", index);
    }
    return 0;
}

數(shù)字分布均勻時（上面的1，2，3這種）：
插值查找
查找次數(shù)：1, 當(dāng)前mid：22
找到了，下標(biāo)是：22
折半查找
查找次數(shù)：1, 當(dāng)前mid：11
查找次數(shù)：2, 當(dāng)前mid：17
查找次數(shù)：3, 當(dāng)前mid：20
查找次數(shù)：4, 當(dāng)前mid：22
找到了，下標(biāo)是：22

不均勻時 上面的int a[] = {1,19,88,109， 如我們要找9999時，還是half快
插值查找
查找次數(shù)：1, 當(dāng)前mid：14
查找次數(shù)：2, 當(dāng)前mid：17
查找次數(shù)：3, 當(dāng)前mid：18
查找次數(shù)：4, 當(dāng)前mid：19
查找次數(shù)：5, 當(dāng)前mid：20
找到了，下標(biāo)是：20
折半查找
查找次數(shù)：1, 當(dāng)前mid：11
查找次數(shù)：2, 當(dāng)前mid：17
查找次數(shù)：3, 當(dāng)前mid：20
找到了，下標(biāo)是：20

還有就是 如果用插值查找，要找得數(shù)不在列表中，容易出現(xiàn)死循環(huán)，大家可以嘗試下，查找一下 9098，死循環(huán)，解決需要加入判斷，看了很多網(wǎng)上的博客，都沒有提高如何解決死循環(huán)；解決方案如下：**
改進(jìn)如下：

int insert_search(int a[], int key, int n) {
    ....
    while(low <= high) {
        // 因計算機整除問題 * 1.0f
        mid = low + (key-a[low])/((a[high]-a[low]) *1.0f)*(high-low);
        printf("查找次數(shù)：%d, 當(dāng)前mid：%d\n", ++time, mid);
        
        // 加入判斷，這里可解決死循環(huán)問題
        // 或者判斷 mid 是否與上一次mid相同，如相同，直接break
        if(mid < low || mid > high) {
            break;
        }
        .....
    }
    
    return index;
}

斐波那契查找（未理解）##

斐波那契查找利用了黃金分割原理來實現(xiàn)。
黃金比例又稱黃金分割，是指事物各部分間一定的數(shù)學(xué)比例關(guān)系，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比，其比值約為1:0.618或1.618:1。

斐波那契數(shù)列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89，從第3個數(shù)開始，后面的數(shù)為前面2個數(shù)的和，隨著，數(shù)組長度的增加，前一個數(shù)比后一個數(shù)的值，越來越接近0.618，利用這個特性，可以將黃金比例運用到查找技術(shù)中。

黃金比例查找也是二分查找的一種提升算法，通過運用黃金比例的概念在數(shù)列中選擇查找點進(jìn)行查找，提高查找效率；

斐波那契查找就是在二分查找的基礎(chǔ)上根據(jù)斐波那契數(shù)列進(jìn)行分割的。
在斐波那契數(shù)列找一個等于略大于查找表中元素個數(shù)的數(shù)F[n]，（如下：第一個while循環(huán)），將原查找表擴(kuò)展為長度為Fn，完成后進(jìn)行斐波那契分割，即F[n]個元素分割為前半部分F[n-1]個元素，后半部分F[n-2]個元素，找出要查找的元素在那一部分并遞歸，直到找到。

void fibonacci(int * F) {
    F[0]=0;
    F[1]=1;
    for(int i=2;i<50;++i)
        F[i]=F[i-1]+F[i-2];
}

int fibonacciSearch(int a[], int key, int n) {
    int i;
    int index = -1;
    int F[50];
    fibonacci(F);
    
    int low = 0;
    int high = n-1;
    
    // 獲取斐波那契分割數(shù)值下標(biāo)
    // 在斐波那契數(shù)列找一個等于略大于查找表中元素個數(shù)的數(shù)
    int k=0;
    while(n > F[k] -1) {
        k++;
    }
    
    // 創(chuàng)建臨時數(shù)組，長度為 F[k] - 1
    int tmp[F[k] - 1];
    for(i=0; i<n; i++) {        // 前面填充為原數(shù)組中的內(nèi)容
        tmp[i] = a[i];
    }
    
    for(i = n; i<F[k]-1; ++i) { // 后面填充為原數(shù)組最后一個元素的值
        tmp[i] = a[n-1];
    }
    
    for(i=0; i<F[k]-1; i++) {
        printf("%d ", tmp[i]);
    }
    printf("\n");
    
    while(low <= high) {
        int mid = low + F[k-1]-1;
        if(key < tmp[mid]) {
            // 查找前半部分，高位指針移動
            high = mid -1;
            k--;
        } else if(key > tmp[mid]) {
            // 查找后半部分，高位指針移動
            low=mid+1;
            k-=2;
        } else {
            if(mid <= high) {
                index = mid;
            } else {
                index = high;
            }
            break;
        }
    }
    
    
    return index;
}

int main(int argc, const char * argv[]) {
    int a[] = {0,16,24,35,47,59,62,73,88,99};
    int key=35;
    int index = fibonacciSearch(a, key, 10);
    if(index > -1) {
        printf("%d\n", index);
    }
    return 0;
}