一、靜態(tài)查找：只查找給定的值，不做其他任何的操作，不改變表結(jié)構(gòu)和數(shù)據(jù)元素

1.查找某特定的關(guān)鍵字是否在表中（判斷性查找）
2.檢索某特定關(guān)鍵字的數(shù)據(jù)元素的各種屬性（檢索性查找）

（一）順序查找（待查找數(shù)據(jù)無序）

順序查找也叫線性查找，它的查找過程：從表中的第一個（最后一個）數(shù)據(jù)元素開始，逐個將給定值和數(shù)據(jù)元素的屬性進(jìn)行對比，如果兩個值相等，查找成功，直到查找到最后所有數(shù)據(jù)元素都不相等，則查找失敗。 示例代碼如下：

 /**
 順序查找（正序）

 @param a 待查找數(shù)組
 @param n 數(shù)組中元素個數(shù)
 @param key 給定值
 @return 目標(biāo)數(shù)據(jù)元素的在數(shù)組的下標(biāo)，若為0則查找失敗
 */
int seq_search(int *a, int n, int key) {
    for (int i = 1; i < n; ++i) {
        if (key == a[i]) {
            return i;
        }
    }
    return 0;
}
                                  程序1.1.1

程序1.1.1是一個簡單的順序查找示例，這個實現(xiàn)是有改進(jìn)空間的，我們可以看到每次for循環(huán)都要進(jìn)行一次防止數(shù)組越界的比較 i < n，這是一個可優(yōu)化點，我們可以在查找方向的末端設(shè)置一個哨兵，這個哨兵是給定值，倘若程序在查找過程中已經(jīng)找到，那么返回的值為目標(biāo)數(shù)據(jù)元素在數(shù)組中的下標(biāo)，否則，為我們設(shè)定的哨兵在數(shù)組的下標(biāo)

/**
 順序查找（正序）
 
 @param a 待查找數(shù)組
 @param n 數(shù)組中元素個數(shù)
 @param key 給定值
 @return 目標(biāo)數(shù)據(jù)元素的數(shù)組下標(biāo)，若為n則查找失敗
 */
int seq_search2(int *a, int n, int key) {
    int i = 0;
    a[n] = key;
    while (a[i] != key) {
        i++;
    }
    return i;
}
                                  程序1.1.2

順序查找的時間復(fù)雜度：

• 在查找成功的情況下：
  目標(biāo)元素在第一個位置，循環(huán)一次查找成功，時間復(fù)雜度為O(1)
  目標(biāo)元素在最后一個位置，循環(huán)n次查找成功，時間復(fù)雜度為O(n)
• 失敗的情況下:
  程序1.1.1需要循環(huán)n次，時間復(fù)雜度為O(n)
  程序1.1.2需要循環(huán)n+1次，時間復(fù)雜度為O(n)

ASL = ∑ Pi * Ci（i = 1， 2， 3 .... n, 即將所有位置查找的概率與查找到該位置比較的次數(shù)的乘積進(jìn)行累和）
Pi：每個位置上的查獲找成功的概率是相同的為 1/n
Ci：查找成功的次數(shù)為（1 + 2 + 3 + ......+ n ）= n * (n + 1) / 2
ASL：平均查找長度為：1/n * { n * (n + 1) / 2} = (n + 1) / 2

因此順序查找的時間復(fù)雜度為O(n)

（二）折半查找（待查找數(shù)據(jù)有序）

折半查找也叫二分查找使用折半查找的前提是帶查找的數(shù)據(jù)是有序的（從小到大），它的查找過程：取待查找數(shù)據(jù)的中間的一個數(shù)據(jù)元素與給定值行比較

• 如果兩者相等，查找成功
• 如果所取數(shù)據(jù)元素比給定值大，則在中間元素的左側(cè)繼續(xù)重復(fù)查找過程，直到查找成功或者失敗
• 如果所取數(shù)據(jù)元素比給定值小，則在中間元素的右側(cè)繼續(xù)重復(fù)查找過程，直到查找成功或者失敗

/**
 折半查找
 
 @param a 待查找數(shù)組
 @param n 數(shù)組中元素個數(shù)
 @param key 給定值
 @return 目標(biāo)數(shù)據(jù)元素的數(shù)組下標(biāo)，若為0則查找失敗
 */
int binary_search(int *a, int n, int key) {
    
    //數(shù)組的第一個元素的下標(biāo)
    int low = 0;
    
    //數(shù)組的最后一個元素的下標(biāo)（數(shù)組下標(biāo)從0開始，n為長度，因此最后一元素的下標(biāo)為0）
    int height = n - 1;
    
    //計算的出數(shù)組中間的數(shù)據(jù)元素的下標(biāo)
    int mid = (low + height) / 2;
    
    //只要待查找的區(qū)域的首部和尾部不相等
    //若是相等，意味著，收尾相接，只有一個元素
    while (low <= height) {
        
        //給定值key和數(shù)組中間的數(shù)據(jù)元素相等
        if (key == a[mid]) {
            
            //查找成功
            return a[mid];
            
        //給定值key比中間的數(shù)據(jù)元素大，則要繼續(xù)下一次查找
        } else if (key > a[mid]) {
            //下一次查找的區(qū)域改變?yōu)?中間值右側(cè)到數(shù)組末尾
            //此時需要改變low的值，進(jìn)而改變mid的值
            //low = mid + 1是因為，mid已經(jīng)取過了，比較過了
            low = mid + 1;
            
        //給定值key比中間的數(shù)據(jù)元素小，則要繼續(xù)下一次查找
        } else {
            //下一次查找的區(qū)域改變?yōu)?中間值左側(cè)到數(shù)組末尾
            //此時需要改變height的值，進(jìn)而改變mid的值
            //height = mid - 1是因為，mid已經(jīng)取過了，比較過了
            height = mid - 1;
        }
        
        //每一趟不成的查找都要重新計算mid的值，從而進(jìn)行下一次的折半查找
        mid = (low + height) / 2;
    }
    
    return 0;
}

二、動態(tài)查找：給定值，在查找過程中插入此數(shù)據(jù)元素不存在則插入給定值的數(shù)據(jù)元素，或者，刪除給定值所對應(yīng)的數(shù)據(jù)元素

1.查找時插入數(shù)據(jù)元素
2.查找時刪除數(shù)據(jù)元素