1.7 查找技術

　　查找：根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素。

　　查找結果：(查找成功：找到;查找不成功：沒找到。)

　　平均查找長度：查找過程中關鍵字和給定值比較的平均次數。

　　1、順序查找

　　基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。

　　在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。

　　順序查找一個具有n個元素的線性表，其平均復雜度為O(n)。

　　下列兩種情況下只能采用順序查找：

　　1)如果線性表是無序表(即表中的元素是無序的)，則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。

　　2)即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。

　　2、二分法查找

　　思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。

　　前提：必須在具有順序存儲結構的有序表中進行。

　　查找過程：

　　1)若中間項(中間項mid=(n-1)/2，mid的值四舍五入取整)的值等于x，則說明已查到;

　　2)若x小于中間項的值，則在線性表的前半部分查找;

　　3)若x大于中間項的值，則在線性表的后半部分查找。

　　特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。

　　*：二分法查找只適用于順序存儲的線性表，且表中元素必須按關鍵字有序(升序)排列。對于無序線性表和線性表的鏈式存儲結構只能用順序查找。在長度為n的有序線性表中進行二分法查找，其時間復雜度為O(log2n)。

　　更多資料：2011計算機等考二級公共基礎知識講義匯總>>

　　相關鏈接：

　　2011計算機等考二級公共基礎知識考試要點匯總

　　全國計算機等考二級：公共基礎知識習題匯總