順序查找

順序查找（Sequential Search），又稱為線性查找。是最基本的查找技術(shù)，它的查找過程，從表中的第一個(gè)（或最后一個(gè)）記錄開始，逐個(gè)進(jìn)行記錄關(guān)鍵字和給定值比較。若某個(gè)記錄的關(guān)鍵字和給定值相等，說明查找成功，如果直到最后一個(gè)（或第一個(gè)）記錄，沒有關(guān)鍵字與給定值相等，說明查找不成功。

//a為數(shù)組,n為查找的數(shù)組個(gè)數(shù),key為要查找的關(guān)鍵字;
int Sequential_Search(int *a,int n,int key){
    for (int i = 0; i <= n - 1 ; i++)
        if (a[i] == key)
            return i;
   //沒找到返回-1
    return -1;
}

折半查找

折半查找（Binary Search）技術(shù)，又稱二分查找。
前提條件是線性表中的記錄必須是關(guān)鍵碼有序的（通常從小到大有序），線性表必須采用順序存儲(chǔ)。
基本思想：

• 在有序表中，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵字相等則查找成功。
• 若給定值小于中間記錄關(guān)鍵字，則在中間記錄的左半?yún)^(qū)繼續(xù)查找。
• 若給定值大于中間記錄關(guān)鍵字，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。
• 重復(fù)以上操作，直到查找成功，或者查找結(jié)束還未找到即查找失敗。

//假設(shè)數(shù)組a,已經(jīng)是有序的(從小到大)
int Binary_Search(int *a,int n,int key){
    
    int low,high,mid;
    //定義最低下標(biāo)為記錄首位
    low = 0;
    //定義最高下標(biāo)為記錄末位
    high = n - 1;
    while (low <= high) {
        
        //折半計(jì)算
        mid = (low + high) /2;
        
        
        if (key < a[mid]) {
            //若key比a[mid] 小,則將最高下標(biāo)調(diào)整到中位下標(biāo)小一位;
            high = mid-1;
        }else if(key > a[mid]){
             //若key比a[mid] 大,則將最低下標(biāo)調(diào)整到中位下標(biāo)大一位;
            low = mid+1;
        }else
            //若相等則說明mid即為查找到的位置;
            return mid;
    }
    
    return 0;
}

折半查找優(yōu)化
折半查找公式為mid = (low + high) / 2 = low + 1/2 (high - low)
考慮將1/2進(jìn)行改進(jìn)，方案如下：

假設(shè)，a[11] = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99} , low = 0, high = 10, 則 a[0] = 0, a[10] = 99, 如果需要查找key = 16，按照常規(guī)折半查找需要進(jìn)行4次才能找到結(jié)果，但是如果用新的共識(shí)，則

我們稱優(yōu)化后的方法為插值查找（Interpolation Search），是根據(jù)查找的關(guān)鍵字key與查找表中的最大最小記錄的關(guān)鍵字比較后的查找方法，核心在于mid的計(jì)算公式關(guān)鍵部分：

//插值查找
int Interpolation_Search(int *a,int n,int key){
    int low,high,mid;
    low = 1;
    high = n;
    
    while (low <= high) {
        
        //插值
        mid = low+ (high-low)*(key-a[low])/(a[high]-a[low]);
    
        if (key < a[mid]) {
            //若key比a[mid]插值小,則將最高下標(biāo)調(diào)整到插值下標(biāo)小一位;
            high = mid-1;
        }else if(key > a[mid]){
            //若key比a[mid]插值 大,則將最低下標(biāo)調(diào)整到插值下標(biāo)大一位;
            low = mid+1;
        }else
            //若相等則說明mid即為查找到的位置;
            return mid;
    }
    
    return 0;
}

斐波拉契查找

斐波拉契查找（Fibonacci Search）是利用斐波拉契數(shù)列為查找的下標(biāo)數(shù)組，而不是折半查找中根據(jù)搜索數(shù)組下標(biāo)來查找，說白了就是利用斐波拉契數(shù)列來生成新的mid。

例如下面F為斐波拉契數(shù)列，a為要查找的記錄數(shù)組，長度為10，low = 1, high = 10, 給定值key = 99，查找a中是否有99，返回相應(yīng)的下標(biāo)：

計(jì)算過程：

1. 由于n = 10, key = 99，F(xiàn)[6] < n < F[7]，得到k = 7, 因?yàn)镕[7] = 13， 而a最大僅有a[10]， 后面的a[11],a[12] 是為賦值的，為了避免之后的數(shù)值比對(duì)數(shù)組越界問題，需要將后續(xù)的2個(gè)元素賦值，a[11] = a[12] = 99。

   
   

2. 此時(shí)mid = low + F[k - 1] - 1 = 1 + F[7 - 1] - 1 = 1 + 8 -1 = 8;
   key > a[8] ---> 99 > 73;
   low = mid + 1 = 8 + 1 = 9;
   k = k - 2 = 7 - 2 = 5;

   
   

3. mid = low + F[k - 1] - 1 = 1 + F[5 - 1] - 1 = 9 + 3 - 1 = 11;
   key = a[11] ---> 99 = 99;
   mid >n , 11 > 10, 則返回n，返回10.
   表示找到key= 99是在數(shù)組a中的位置是10的位置上。

key = 99是處在邊緣的值，我們可以假設(shè)key = 59，來看看在a數(shù)組中間的數(shù)值計(jì)算過程又是怎樣的？

計(jì)算過程：

1. n = 10, 同上面一樣，得到k = 7, F[7] = 13, 補(bǔ)齊后兩位數(shù)值為a[11] = a[12] = a[10] = 99;

2. mid = low + F[k - 1] - 1 = 1 + F[7 - 1] - 1=1 + 8 - 1 = 8;
   key < a[8] ---> 59 < 73;
   high = mid - 1 = 8 - 1 = 7;
   k = k - 1 = 6;

   
   

3. mid = low + F[k - 1] = 1 + F[6 - 1] - 1 = 1 + 5 -1 = 5;
   key > a[5] ---> 59 > 47;
   low = mid + 1 = 5 + 1 = 6;
   k = k - 2 = 4;

   
   

4. mid = low +F[k - 1] - 1 = 6 + F[4 - 1] - 1 = 7;
   key < a[7] ---> 59 < 62
   high = mid - 1 = 6;
   k = k - 1 = 3;

   
   

5. mid = low + F[k - 1] - 1 = 6 + 1 - 1 = 6;
   key = a[6];
   mid < n ; 6 < 10, 返回 6;
   找到key = 59在數(shù)組a中的位置為6。

結(jié)論：斐波拉契查找就是利用mid = low + F[k -1] - 1 這個(gè)公式來計(jì)算出mid的所在位置。然后比較給定值與a[mid]的大小，然后繼續(xù)或結(jié)束。

int F[100]; /* 斐波那契數(shù)列 */
//初始化數(shù)列
    F[0]=0;
    F[1]=1;
    for(i = 2;i < 100;i++)
    {
        F[i] = F[i-1] + F[i-2];
    }

//計(jì)算過程
int Fibonacci_Search(int *a,int n,int key){
  
    int low,high,mid,i,k;
    //最低下標(biāo)為記錄的首位;
    low = 1;
    //最高下標(biāo)為記錄的末位;
    high = n;
    k = 0;
    
    //1.計(jì)算n為斐波拉契數(shù)列的位置;
    while (n > F[k]-1) {
        k++;
    }
    
    //2.將數(shù)組a不滿的位置補(bǔ)全值;
    for(i = n;i < F[k]-1;i++)
        a[i] = a[n];
    
    //3.
    while (low <= high) {
        
        //計(jì)算當(dāng)前分隔的下標(biāo);
        mid = low+F[k-1]-1;
        
        
        if (key < a[mid]) {
            //若查找的記錄小于當(dāng)前分隔記錄;
            //將最高下標(biāo)調(diào)整到分隔下標(biāo)mid-1處;
            high = mid-1;
            //斐波拉契數(shù)列下標(biāo)減1位;
            k = k-1;
            
        }else if(key > a[mid]){
            //若查找的記錄大于當(dāng)前的分隔記錄;
            //最低下標(biāo)調(diào)整到分隔下標(biāo)mid+1處
            low = mid+1;
            //斐波拉契數(shù)列下標(biāo)減2位;
            k = k-2;
            
        }else{
            if (mid <= n) {
                //若相等則說明,mid即為查找的位置;
                return mid;
            }else
            {
                //若mid>n,說明是補(bǔ)全數(shù)值,返回n;
                return n;
            }
        }
    }
    return 0;
}

總結(jié)

綜上幾種數(shù)據(jù)查找的方法，說白了就是對(duì)mid的計(jì)算公式的不同，從而達(dá)到不同的效率。