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

胡鋒

摘 要：對分查找是一種效率很高的查找方法，是浙教版《算法與程序設(shè)計(jì)》的重點(diǎn)內(nèi)容之一。學(xué)生容易入門，但很難熟練應(yīng)用。本文通過對對分查找算法的分析，探討解題的一般策略，增強(qiáng)學(xué)生靈活應(yīng)變的能力。

關(guān)鍵詞：對分查找;核心代碼;思路;規(guī)律

一、對分查找算法的特點(diǎn)

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

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

對分查找既然要對分，就必須指定對分點(diǎn)，即中點(diǎn)位置，假設(shè)L為左端點(diǎn)位置，R為右端點(diǎn)位置，M為中點(diǎn)位置。中點(diǎn)M的表示方法有很多，不同方法也不盡相同。常見為M=（L+R）＼2， M=（L+R+1）＼2，這兩種方法的主要區(qū)別是當(dāng)數(shù)據(jù)個(gè)數(shù)是偶數(shù)時(shí)，中間位置是兩個(gè)數(shù)，前者取左邊一個(gè)，后者取右邊一個(gè)。假設(shè)現(xiàn)有數(shù)組A中有N個(gè)數(shù)據(jù)并升序排列，查找key所在的位置。如果中間位置M的數(shù)A（M）等于key，則M就是結(jié)果;如果中間位置M的數(shù)A（M）大于key，則說明key只能到M之前去尋找（因?yàn)楹竺娴臄?shù)更大）;如果中間位置M的數(shù)A（M）小于key，則說明key只能到M之后去尋找（因?yàn)榍懊娴臄?shù)更小）。 重復(fù)上面的過程，直到找到數(shù)據(jù)或找完數(shù)據(jù)。

將上述文字描述變?yōu)閂B核心代碼，如下：

L=1? ：? ? ? R=N

Do While L<=R? ‘L<=R表示還有數(shù)據(jù)，至少1個(gè)數(shù)據(jù)

M=（L+R） ＼ 2

If? ? a（M）=key? Then

Exit Do? ? ‘找到key后退出

ElseIf? a（M）>key Then

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

Else

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

End If

Loop

上述代碼運(yùn)行結(jié)束后，如何判斷是否找到key？

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

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

1 L<=R? ? ? （此時(shí)必定是強(qiáng)制退出循環(huán)）

2 A（M）=key? （這是強(qiáng)制退出循環(huán)的前提條件）

3 flag=True （設(shè)置標(biāo)記，初始為False，找到時(shí)設(shè)為True）

引入標(biāo)記的核心代碼如下：

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，代碼可讀性高。

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

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

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

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

舉例：

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

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

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

從本質(zhì)上來看都是搜索邊界，一個(gè)內(nèi)邊界，一個(gè)外邊界。

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

我們以找第一個(gè)等于6的位置為例，當(dāng)中間值等于6時(shí)，可能前面還有6，因此應(yīng)該繼續(xù)向前尋找。

查找第一次出現(xiàn)key的位置（假定數(shù)據(jù)為升序），參考代碼如下：

L=1? ：? ?R=n

Do? While L

m=（L+R） ＼ 2

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

L=m+1

Else? ? ? ? ? ? ? ‘中間值太大和相等時(shí)都繼續(xù)向前找

R=m-1

End If

Loop

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

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

四、對分查找算法的規(guī)律

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

五、結(jié)語

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

參考文獻(xiàn)

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