考點7 查找技術

1.順序查找

順序查找一般是指在線性表中查找指定的元素。其基本思路是：從表中的第一個元素開始，依次將線性表中的元素與被查找元素進行比較，直到兩者相符，查到所要找的元素為止。否則，表中沒有要找的元素，查找不成功。

在最好的情況下，第一個元素就是要查找的元素，則比較次數為1次。

在最壞的情況下，順序查找需要比較n次。

在平均情況下，需要比較n／2次。因此查找算法的時間復雜度為O（n）。

在下列兩種情況下只能夠采取順序查找：

●如果線性表中元素的排列是無序的，則無論是順序存儲結構還是鏈式存儲結構，都只能用順序查找；

真考鏈接

考核概率為35%，考生需要理解該考點內容，主要是順序查找與二分查找的概念，以及一些查找的方法。

●即便是有序線性表，若采用鏈式存儲結構，只能進行順序查找。

2.二分查找

使用二分法查找的線性表必須滿足以下兩個條件：

●順序存儲結構；

●線性表是有序表。

所謂有序表，是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

對于長度為n的有序線性表，利用二分法查找元素x的過程如下。

（1）將x與線性表的中間項進行比較。

（2）若中間項的值等于x，則查找成功，結束查找。

（3）若x小于中間項的值，則在線性表的前半部分以二分法繼續查找。

（4）若x大于中間項的值，則在線性表的后半部分以二分法繼續查找。

這樣反復進行查找，直到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。

當有序線性表為順序存儲時采用二分查找的效率要比順序查找高得多。對于長度為n的有序線性表，在最壞的情況下，二分查找只需比較log2n次，而順序查找則需要比較n次。

真題精選

下列數據結構中，能用二分法進行查找的是______。

A）順序存儲的有序線性表

B）線性鏈表

C）二叉鏈表

D）有序線性鏈表

【答案】A

【解析】二分法查找只適用于順序存儲的有序表。所謂有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。