1.5查找技術(shù)
    考點(diǎn)9 順序查找
    考試鏈接：
    考點(diǎn)9在筆試考試中考核幾率在30%，一般出現(xiàn)選擇題中，分值為2分，讀者應(yīng)該具體掌握順序查找的算法。
    查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。從線性表的第一個(gè)元素開(kāi)始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進(jìn)行了比較但都不相等，則表示查找失敗。
    在下列兩種情況下也只能采用順序查找：
    （1）如果線性表為無(wú)序表，則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，只能用順序查找。
    （2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。
    考點(diǎn)10 二分法查找
    考試鏈接：
    考點(diǎn)10在筆試考試中考核幾率為30%，一般出現(xiàn)填空題中，分值為2分，考核比較多查找的比較次數(shù)，讀者應(yīng)該具體掌握二分查找法的算法。
    二分法只適用于順序存儲(chǔ)的，按非遞減排列的有序表，其方法如下：
    設(shè)有序線性表的長(zhǎng)度為n，被查找的元素為i，
    （1）將i與線性表的中間項(xiàng)進(jìn)行比較；
    （2）若i與中間項(xiàng)的值相等，則查找成功；
    （3）若i小于中間項(xiàng)，則在線性表的前半部分以相同的方法查找；
    （4）若i大于中間項(xiàng)，則在線性表的后半部分以相同的方法查找。
    疑難解答：二分查找法適用于哪種情況？
    二分查找法只適用于順序存儲(chǔ)的有序表。在此所說(shuō)的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。
    這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0為止。
    對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。