2011計算機二級考試公共基礎(chǔ)知識講義：第1章(7)

　　1.7 查找技術(shù)

　　查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。

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

　　平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。

　　1、順序查找

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

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

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

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

　　1)如果線性表是無序表(即表中的元素是無序的)，則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯�結(jié)構(gòu)，都只能用順序查找。

　　2)即使是有序線性表，如果采用鏈?zhǔn)酱鎯�結(jié)構(gòu)，也只能用順序查找。

　　2、二分法查找

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

　　前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進(jìn)行。

　　查找過程：

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

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

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

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

　　*：二分法查找只適用于順序存儲的線性表，且表中元素必須按關(guān)鍵字有序(升序)排列。對于無序線性表和線性表的鏈?zhǔn)酱鎯�結(jié)構(gòu)只能用順序查找。在長度為n的有序線性表中進(jìn)行二分法查找，其時間復(fù)雜度為O(log2n)。

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

　　相關(guān)鏈接：

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

　　全國計算機等考二級：公共基礎(chǔ)知識習(xí)題匯總