查找 -數據結構

幾種查找算法:順序查找，折半查找，分塊查找，散列表

一、順序查找的基本思想：

 從表的一端開始，向另一端逐個按給定值kx 與關鍵碼進行比較，若找到，查找成功，并給出數據元素在表中的位置；若整個表檢測完，仍未找到與kx 相同的關鍵碼，則查找失敗，給出失敗信息。

說白了就是，從頭到尾，一個一個地比，找著相同的就成功，找不到就失敗。很明顯的缺點就是查找效率低。

【適用性】：適用于線性表的順序存儲結構和鏈式存儲結構。

平均查找長度=（n+1）/2.

【順序查找優缺點】：

缺點:是當n 很大時，平均查找長度較大，效率低；

優點:是對表中數據元素的存儲沒有要求。另外，對于線性鏈表，只能進行順序查找。

二、有序表的折半查找基本思想：

在有序表中，取中間元素作為比較對象，若給定值與中間元素的關鍵碼相等，則查找成功；若給定值小于中間元素的關鍵碼，則在中間元素的左半區繼續查找；若給定值大于中間元素的關鍵碼，則在中間元素的右半區繼續查找。不斷重復上述查找過程，直到查找成功，或所查找的區域無數據元素，查找失敗。

【步驟】

① low=1；high=length； // 設置初始區間
② 當low>high 時，返回查找失敗信息// 表空，查找失敗
③ low≤high，mid=(low+high)/2; //確定該區間的中點位置
      a. 若kx<tbl.elem[mid].key，high = mid-1；轉② // 查找在左半區進行
      b. 若kx>tbl.elem[mid].key，low  = mid+1； 轉② // 查找在右半區進行
      c. 若kx=tbl.elem[mid].key，返回數據元素在表中位置// 查找成功

有序表按關鍵碼排列如下：

7，14，18，21，23，29，31，35，38，42，46，49，52

在表中查找關鍵碼為14 的數據元素:

 【算法實現】

int Binary_Search(ElemType a[], ElemType kx, int length)  
    {  
    int mid,low,high, flag = 0;  
    low = 0; high = length;                   /* ①設置初始區間*/  
    while(low <= high)                        /* ②表空測試*/  
    {    /* 非空,進行比較測試*/  
        mid = (low + high)/2;                /* ③得到中點*/  
        if(kx < a[mid]) high = mid-1;        /* 調整到左半區*/  
        else if(kx > a[mid]) low = mid+1;    /* 調整到右半區*/  
        else {                                /* 查找成功,元素位置設置到flag 中*/  
            flag=mid;  
            break;  
        }                          
    }  
    return flag;  
}

【性能分析】

平均查找長度=Log2⁽ⁿ⁺¹⁾-1

 從折半查找過程看，以表的中點為比較對象，并以中點將表分割為兩個子表，對定位到的子表繼續這種操作。所以，對表中每個數據元素的查找過程，可用二叉樹來描述，稱這個描述查找過程的二叉樹為判定樹。

                                                  (7，14，18，21，23，29，31，35，38，42，46，49，52)折半查找的判定樹

可以看到，查找表中任一元素的過程，即是判定樹中從根到該元素結點路徑上各結點關鍵碼的比較次數，也即該元素結點在樹中的層次數。對于n 個結點的判定樹，樹高為k，則有2k-1 -1<n≤2k-1，即k-1<log2(n+1)≤k，所以k= 。因此，折半查找在查找成功時，所進行的關鍵碼比較次數至多為。

接下來討論折半查找的平均查找長度。為便于討論，以樹高為k 的滿二叉樹(n=2k-1)為例。假設表中每個元素的查找是等概率的，即Pi= ，則樹的第i 層有2i-1 個結點，因此，折半查找的平均查找長度為：

所以，折半查找的時間效率為O(log2n)。

注：

雖然折半查找的效率高，但是要將表按關鍵字排序。而排序本身是一種很費時的運算，所以二分法比較適用于順序存儲結構。為保持表的有序性，在順序結構中插入和刪除都必須移動大量的結點。因此，折半查找特別適用于那種一經建立就很少改動而又經常需要查找的線性表。

三、分塊查找（索引查找）的基本思想：

分塊查找又稱索引順序查找，是對順序查找的一種改進。分塊查找要求將查找表分成 若干個子表，并對子表建立索引表，查找表的每一個子表由索引表中的索引項確定。索引 項包括兩個字段：關鍵碼字段(存放對應子表中的最大關鍵碼值) ；指針字段(存放指向對 應子表的指針) ，并且要求索引項按關鍵碼字段有序。查找時，先用給定值kx 在索引表中 檢測索引項，以確定所要進行的查找在查找表中的查找分塊(由于索引項按關鍵碼字段有序，可用順序查找或折半查找) ，然后，再對該分塊進行順序查找。

如關鍵碼集合為：

                           （22，12，13，9，20，33，42，44，38，24，48，60，58，74，49，86，53）

按關鍵碼值31，62，88 分為三塊建立的查找表及其索引表如下：

設表共n個結點，分b塊，s=n/b

(分塊查找索引表)平均查找長度=Log2^{（n/s+1）+s/2}

(順序查找索引表)平均查找長度=(S²+2S+n)/(2S)

注：

分塊查找的優點是在表中插入或刪除一個記錄時，只要找到該記錄所屬塊，就在該塊中進行插入或刪除運算（因塊內無序，所以不需要大量移動記錄）。它主要代價是增加一個輔助數組的存儲控件和將初始表分塊排序的運算。

它的性能介于順序查找和二分查找之間。

轉自：http://blog.csdn.net/hguisu/article/details/7776091