1.7 查找技術(shù)
查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。
查找結(jié)果：（查找成功：找到；查找不成功：沒(méi)找到。）
平均查找長(zhǎng)度：查找過(guò)程中關(guān)鍵字和給定值比較的平均次數(shù)。
1、順序查找
基本思想：從表中的第一個(gè)元素開(kāi)始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒(méi)有要找的元素，查找不成功。
在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情況下需要比較n次。
順序查找一個(gè)具有n個(gè)元素的線性表，其平均復(fù)雜度為O（n）。
下列兩種情況下只能采用順序查找：
1）如果線性表是無(wú)序表（即表中的元素是無(wú)序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。
2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。
2、二分法查找
思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。
前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。
查找過(guò)程：
1）若中間項(xiàng)（中間項(xiàng)mid=(n-1)/2，mid的值四舍五入取整）的值等于x，則說(shuō)明已查到；
2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；
3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。
特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。
*：二分法查找只適用于順序存儲(chǔ)的線性表，且表中元素必須按關(guān)鍵字有序（升序）排列（注釋1）。對(duì)于無(wú)序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找。在長(zhǎng)度為n的有序線性表中進(jìn)行二分法查找，其時(shí)間復(fù)雜度為O（log2n）。
注釋1：允許相鄰元素值相等。