淺析對分查找算法與解題思路

胡鋒

摘 要：對分查找是一種效率很高的查找方法，是浙教版《算法與程序設計》的重點內容之一。學生容易入門，但很難熟練應用。本文通過對對分查找算法的分析，探討解題的一般策略，增強學生靈活應變的能力。

關鍵詞：對分查找;核心代碼;思路;規律

一、對分查找算法的特點

對分查找從字面上看有對分二字，大意就是每次查找，數據規模減半，一般情況下比順序查找快很多，查詢效率也較高。N個元素，采用順序查找算法，最壞的情況是查找N次，而采用對分查找算法，最壞的情況是查找Int（log2N+1）。顯然當數據規模較大時，對分查找效率遠勝順序查找。對分查找雖然速度快，但對數據有要求，不能雜亂無序，必須是升序或降序排列，或者是按照某種規則有序排列的。

二、對分查找算法的核心代碼

對分查找既然要對分，就必須指定對分點，即中點位置，假設L為左端點位置，R為右端點位置，M為中點位置。中點M的表示方法有很多，不同方法也不盡相同。常見為M=（L+R）＼2， M=（L+R+1）＼2，這兩種方法的主要區別是當數據個數是偶數時，中間位置是兩個數，前者取左邊一個，后者取右邊一個。假設現有數組A中有N個數據并升序排列，查找key所在的位置。如果中間位置M的數A（M）等于key，則M就是結果;如果中間位置M的數A（M）大于key，則說明key只能到M之前去尋找（因為后面的數更大）;如果中間位置M的數A（M）小于key，則說明key只能到M之后去尋找（因為前面的數更小）。 重復上面的過程，直到找到數據或找完數據。

將上述文字描述變為VB核心代碼，如下：

L=1? ：? ? ? R=N

Do While L<=R? ‘L<=R表示還有數據，至少1個數據

M=（L+R） ＼ 2

If? ? a（M）=key? Then

Exit Do? ? ‘找到key后退出

ElseIf? a（M）>key Then

R=M-1? ? ‘中間位置的數太大了，到M之前去找

Else

L=M+1? ?‘中間位置的數太小了，到M之后去找

End If

Loop

上述代碼運行結束后，如何判斷是否找到key？

要弄清楚這個問題，首先我們知道該算法主體是一個循環結構，結束循環的方式有兩個。其一，L>R，使得Do While語句循環條件不成立;其二，找到key，通過Exit Do語句，強制結束循環。顯然這兩個方式不可能同時起作用，因此找到key時必定強制退出，此時依然L<=R，而沒有找到key時，必定是L>R來結束循環。

我們可以通過以下方式來判斷找到key了：

1 L<=R? ? ? （此時必定是強制退出循環）

2 A（M）=key? （這是強制退出循環的前提條件）

3 flag=True （設置標記，初始為False，找到時設為True）

引入標記的核心代碼如下：

L=1? ：? ?R=N? ?：? ? flag=False

Do? While L<=R? And Not flag

M=（L+R） ＼ 2

If? a（M）=key? Then

flag=True

ElseIf? a（M）>key Then

R=M-1

Else

L=M+1

End If

Loop

最后只要判斷flag即可知道是否找到Key，代碼可讀性高。

熟練掌握核心代碼是解題的基礎，也是突破各種對分查找變式的關鍵所在。

三、各種對分查找變式常用解題思路

邊界搜索問題，比如在有序數據中查找重復數據key的第一個或最后一個位置;又如找一個小于key的最大值或大于key的最小值。

雖然這類問題都可以利用核心代碼找到等于key的位置，然后按順序向前或向后依次搜尋來解決。但這部分就變成順序查找了，失去了對分查找的效率。因此優先考慮使用對分查找來解決問題。

舉例：

從表格中可以看出位置4至9都是6。

查找第1個6的位置是4，最后一個6的位置是9 。

查找小于6的最大值的位置是3，大于6的最小值的位置是10。

從本質上來看都是搜索邊界，一個內邊界，一個外邊界。

核心代碼用來解決這類問題時，必定需要進行適當改變。中間值太小或太大的處理方式沒什么不同，主要不同在于核心代碼中找到key就退出了，而在邊界搜索時，找到key時問題還沒有求解，故不能結束。本例中，假定中間位置采用M=（L+R）＼2，則第一次找到位置是6，顯然6不是問題的解。

我們以找第一個等于6的位置為例，當中間值等于6時，可能前面還有6，因此應該繼續向前尋找。

查找第一次出現key的位置（假定數據為升序），參考代碼如下：

L=1? ：? ?R=n

Do? While L

m=（L+R） ＼ 2

If? a（m）< key? Then ‘注意這里判斷中間值太小的情況

L=m+1

Else? ? ? ? ? ? ? ‘中間值太大和相等時都繼續向前找

R=m-1

End If

Loop

如果key值在序列中，則L就是第1個出現的位置，而R就是這第一個數之前的位置（換句話來說，就是比key小的最大值的位置，當然如果R=0了，說明位置R實際不存在，即序列中沒有數比key小）。如果key值不在序列中，L和R又表示什么呢（此時L=R+1，循環結束條件）？如果L和R都存在（1～n），那么L表示第一個比key大的數的位置，R表示最后一個比key小的數的位置，即如果key要插入到序列中使序列依然有序，那么key只能放在位置R與L之間;如果位置L不存在（此時R=n，L=n+1），說明key大于序列中所有數;如果位置R不存在（此時L=1，R=0），說明key小于序列中所有數。

從上面的分析可以發現找一個小于key的最大值位置的代碼基本一致，只是前者用L，后者用R。

四、對分查找算法的規律

一般情況下，判斷對分查找是向前還是向后查找并不是特別難，難的是相等時該向前還是向后查找，以及調整端點位置時該調整到哪里。通過前面的分析，我們可以得出以下規律：如果要找第一次出現的位置，相等時繼續向前查找;如果要找最后一次出現的位置，相等時繼續向后查找。至于位置變化時，是否要加減一，關鍵看中間點是否是可能的解，如果是則保留，反之則加減一。

五、結語

對分查找是一種效率很高的查找方法，在實際生活中應用很廣，也是信息技術選考中的一個高頻考點，有一定的難度。要熟練掌握對分查找算法，就要熟悉它的工作原理，熟識它的核心代碼，善于分析問題，了解一般規律。對分查找雖然效率高，但前提是數據有序，這一點必須牢記。

參考文獻

[1]曾偉鋒.高中信息科技計算思維教學實踐——以對分查找算法為例[J].中國信息技術教育，2018（Z2）.