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)酱鎯Y(jié)構(gòu),都只能用順序查找。
2)即使是有序線性表,如果采用鏈?zhǔn)酱鎯Y(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)酱鎯Y(jié)構(gòu)只能用順序查找。在長度為n的有序線性表中進(jìn)行二分法查找,其時間復(fù)雜度為O(log2n)。
更多資料:2011計算機等考二級公共基礎(chǔ)知識講義匯總>>
相關(guān)鏈接:
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |