（七）查找技術(shù)
查找即是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。
1．順序查找
順序查找又稱順序搜索。一般是在線性表中查找指定的元素。
基本操作方法是：
從線性表的第一個(gè)元素開始，與被查元素進(jìn)行比較，相等則查找成功，否則繼續(xù)向后查找。如果所有的元素均查找完畢后都不相等，則該元素在指定的線性表中不存在。
順序查找的情況：要查找的元素在線性表的第一個(gè)元素，則查找效率；如果要查找的元素在線性表的最后或根本不存在，則查找需要搜索所有的線性表元素，這種情況是最差情況。
對于線性表而言，順序查找效率很低。但對于以下的線性表，也只能采用順序查找的方法：
線性表為無序表，即表中的元素沒有排列不是按大小順序進(jìn)行排列的，這類線性表不管它的存儲方式是順序存儲還是鏈?zhǔn)酱鎯?，都只能按順序查找方式進(jìn)行查找
即使是有序線性表，如果采用鏈?zhǔn)酱鎯?，也只能采用順序查找方?BR> 例如，現(xiàn)有線性表：7、2、1、5、9、4，要在序列中查找元素6，查找的過程是：
整個(gè)線性表的長度為5
查找計(jì)次n=1，將元素6與序列的第一個(gè)7元素進(jìn)行比較，不等，繼續(xù)查找
n=2，將6與第二個(gè)元素2進(jìn)行比較，不等，繼續(xù)
n=3，將6與第三個(gè)元素1進(jìn)行比較，不等，繼續(xù)
n=4，將6與第四個(gè)元素5進(jìn)行比較，不等，繼續(xù)
n=5，將6與第五個(gè)元素9進(jìn)行比較，不等，繼續(xù)
n=6，將6與第六個(gè)元素4進(jìn)行比較，不等，繼續(xù)
n=7，超出線性表的長度，查找結(jié)束，則該表中不存在要查找的元素。
2．二分查找
二分查找只適用于順序存儲的有序表。此處所述的有序表是指線性中的元素按值非遞減排列（即由小到大，但允許相鄰元素值相等）。
二分查找的方法如下：
將要查找的元素與有序序列的中間元素進(jìn)行比較：
如果該元素比中間元素大，則繼續(xù)在線性表的后半部分（中間項(xiàng)以后的部分）進(jìn)行查找
如果要查找的元素的值比中間元素的值小，則繼續(xù)在線性表的前半部分（中間項(xiàng)以前的部分）進(jìn)行查找
這個(gè)查找過程一直按相同的順序進(jìn)行下去，一直到查找成功或子表長度為0（說明線性表中沒有要查找的元素）
有序線性表的二分法查找，條件是必須這個(gè)有序線性表的存儲方式是順序存儲的。它的查找效率比順序查找要高得多，它的最壞情況的查找次數(shù)是log2n次，而順序查找的最壞情況的查找次數(shù)是n次。
當(dāng)然，二分查找的方法也支持順序存儲的遞減序列的線性表。
有非遞減有序線性表：1、2、4、5、7、9，要查找元素6。查找的方法是：
序列長度為n=6，中間元素的序號m=[(n+1)/2]=3
查找計(jì)次k=1，將元素6與中間元素即元素4進(jìn)行比較，不等，6>4
查找計(jì)次k=2，查找繼續(xù)在后半部分進(jìn)行，后半部分子表的長度為3，計(jì)算中間元素的序號：m=3+[(3+1)/2]=5，將元素與后半部分的中間項(xiàng)進(jìn)行比較，即第5個(gè)元素中的7進(jìn)行比較，不等，6<7
查找計(jì)次k=3，繼續(xù)查找在后半部分序列的前半部分子序列中查找，子表長度為1，則中間項(xiàng)序號即為m=3+[(1+1)/2]=4，即與第4個(gè)元素5進(jìn)行比較，不相等，繼續(xù)查找的子表長度為0，則查找結(jié)束