1.1.6 查找技術

所謂查找是指在一個給定的數(shù)據(jù)結構中查找某個指定的元素。在查找的過程中，涉及查找的方法等問題，通常，根據(jù)不同的數(shù)據(jù)結構，應采用不同的查找方法。

1.順序查找

順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：

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

在進行順序查找過程中，如果線性表中的第一個元素就是被查找元素，則只需做一次比較即可查找成功，查找效率最高；但如果被查找的元素是線性表中的最后一個元素，或者被查元素根本不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行比較，這是順序查找的最壞情況。在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較。

由此可以看出，對于大的線性表來說，順序查找的效率是很低的。雖然順序查找的效率不高，但在下列兩種情況下也只能采用順序查找。

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

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

2.二分法查找

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

設有序線性表的長度為n，被查元素為x，則二分查找的方法如下。

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

1）若中間項的值等于x，則說明查找成功，查找結束。

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

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

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