胡鋒

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

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

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

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

二、對(duì)分查找算法的核心代碼

對(duì)分查找既然要對(duì)分，就必須指定對(duì)分點(diǎn)，即中點(diǎn)位置，假設(shè)L為左端點(diǎn)位置，R為右端點(diǎn)位置，M為中點(diǎn)位置。中點(diǎn)M的表示方法有很多，不同方法也不盡相同。常見(jiàn)為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，則說(shuō)明key只能到M之前去尋找（因?yàn)楹竺娴臄?shù)更大）;如果中間位置M的數(shù)A（M）小于key，則說(shuō)明key只能到M之后去尋找（因?yàn)榍懊娴臄?shù)更?。?。 重復(fù)上面的過(guò)程，直到找到數(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è)問(wèn)題，首先我們知道該算法主體是一個(gè)循環(huán)結(jié)構(gòu)，結(jié)束循環(huán)的方式有兩個(gè)。其一，L>R，使得Do While語(yǔ)句循環(huán)條件不成立;其二，找到key，通過(guò)Exit Do語(yǔ)句，強(qiáng)制結(jié)束循環(huán)。顯然這兩個(gè)方式不可能同時(shí)起作用，因此找到key時(shí)必定強(qiáng)制退出，此時(shí)依然L<=R，而沒(méi)有找到key時(shí)，必定是L>R來(lái)結(jié)束循環(huán)。

我們可以通過(guò)以下方式來(lái)判斷找到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è)為T(mén)rue）

引入標(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ǔ)，也是突破各種對(duì)分查找變式的關(guān)鍵所在。

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

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

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

舉例：

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

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

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

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

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

我們以找第一個(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ù)之前的位置（換句話來(lái)說(shuō)，就是比key小的最大值的位置，當(dāng)然如果R=0了，說(shuō)明位置R實(shí)際不存在，即序列中沒(méi)有數(shù)比key?。Ｈ绻鹝ey值不在序列中，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），說(shuō)明key大于序列中所有數(shù);如果位置R不存在（此時(shí)L=1，R=0），說(shuō)明key小于序列中所有數(shù)。

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

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

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

五、結(jié)語(yǔ)

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

參考文獻(xiàn)

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