1.7　查找技術

考點1　順序查找（順序搜索）

（1）基本方法

從線性表的第一個元素開始，依次將線性表中的元素與被查元素進行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失敗）。

（2）以下兩種情況只能采用順序查找：

①線性表為無序表（即表中元素的排列是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。

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

（3）順序查找的缺陷：效率太低

考點2　二分法查找（對分查找）

（1）適用范圍

只適用于順序存儲的有序表，在此所說的有序表是指線性表中元素按值非遞減排列。

（2）具體方法

設有序線性表的長度為n，被查元素為x，則：

①將x與線性表的中間項進行比較：若中間項的值等于x，則說明查到，查找結束；

②若x小于中間項的值，則在線性表的前半部分（即中間項以前的部分）以相同的方法進行查找；

③若x大于中間項的值，則在線性表的后半部分（即中間項以后的部分）以相同的方法進行查找；

④這個過程一直進行到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。

【真題演練】

在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數是（　　）。[2013年9月真題]

A．O(n)

B．O(n²)

C．O(log₂n)

D．O(nlog₂n)

【答案】C

【解析】二分查找的最壞情況是不斷的二分直至無法再分時，仍然沒有查找成功。對于有序的線性表，二分查找法只需比較log₂n次。答案選擇C選項。