從選考試題看對(duì)分查找算法問題的 解題策略

傅琳璐

對(duì)分查找算法作為程序設(shè)計(jì)中的經(jīng)典算法之一，是一種高效的查找方法?？v觀浙江省2015—2020年的信息技術(shù)選考試題，可發(fā)現(xiàn)對(duì)分查找算法是每年選考試題中的必考內(nèi)容。從最開始簡(jiǎn)單的查找區(qū)間計(jì)算，到算法思想應(yīng)用……再到今年的對(duì)分查找變形程序分析，試題考查內(nèi)容的角度在變，難度也在逐步增大。這就要求學(xué)生在平時(shí)的學(xué)習(xí)過程中不僅要深入理解對(duì)分查找算法思想，建立良好的算法思維和計(jì)算思維，還要掌握一定的解題策略，具備良好的解題能力，只有這樣才能在選考考試中做到“倉里有糧，心中不慌”。

● 勤用列表追蹤查找過程

例1.（2017.4選考真題）某對(duì)分查找算法的VB程序段如圖1所示。數(shù)組元素a（1）到a（10）的值依次為“8，17，24，30，36，40，55，58，61，66”，文本框Text1中輸入的值是30，執(zhí)行該程序段，文本框Text2中顯示的是（? ）。

A.40 24? ?B.40 24 36

C.36 24? ?D.36 17 24

剖析：此題為對(duì)分查找過程分析題，查找鍵key值已知，所求文本框Text2中顯示的內(nèi)容為對(duì)分查找過程中找到key值之前依次訪問到的數(shù)據(jù)a（m），解題時(shí)可用列表法記錄對(duì)分查找過程中各個(gè)變量值的變化（如下表）。

點(diǎn)評(píng)：列表法是解決對(duì)分查找問題最簡(jiǎn)單有效的方法，過程清晰，一目了然。用列表法將對(duì)分查找算法執(zhí)行一遍，可以清楚準(zhǔn)確地觀察到查找過程中各個(gè)變量值的變化，同時(shí)還可以幫助學(xué)生鞏固算法過程，加深對(duì)算法思想的理解，答題正確率高，非常適合算法的初學(xué)者。但是列表法比較費(fèi)時(shí)，在遇到對(duì)分查找次數(shù)較多或查找鍵key值未知，查找過程不唯一的問題時(shí)，解題效率不高。

● 活用特征判斷程序結(jié)果

例2.（2017.11選考真題）某對(duì)分查找算法的VB程序段如下頁圖2所示，數(shù)組元素a（1）到a（7）的值依次為“24，35，38，41，45，69，78”。若該程序段執(zhí)行后，文本框Text1中顯示的內(nèi)容可能是（? ?）。

A.RL? ? B.LMR

C.RLR? ? D.LRLM

剖析：此題為對(duì)分查找過程分析題，key值未知，查找過程不唯一，不適用列表法求解，但分析題目發(fā)現(xiàn)本題可直接運(yùn)用對(duì)分查找的特征結(jié)論來排除部分選項(xiàng)。

特征：①無論查找鍵key是否在被查找數(shù)組中，n個(gè)數(shù)的對(duì)分查找最多查找次數(shù)為int（log2n）+1。②如果查找鍵key在被查找數(shù)組中，n個(gè)數(shù)的對(duì)分查找最少查找次數(shù)為1次;如果查找鍵key不在被查找數(shù)組中，n個(gè)數(shù)的對(duì)分查找最少查找次數(shù)為int（log2n+1）。

分析程序可知，程序有兩個(gè)結(jié)束出口：一是查找成功立即退出，字符串s以“M”結(jié)尾;二是查找不成功，字符串s中沒有“M”。因此“M”不可能在字符串s中間，排除B選項(xiàng);查找不成功時(shí)，對(duì)分查找最少要查找int（log2n+1）=3次，排除A選項(xiàng);n個(gè)數(shù)的對(duì)分查找次數(shù)最多查找int（log2n）+1=3次，排除D選項(xiàng)。

點(diǎn)評(píng)：用對(duì)分查找算法的特征結(jié)論可以快速準(zhǔn)確地完成試題分析，達(dá)到事半功倍的效果，對(duì)分查找算法還有如下3個(gè)特征：①如果查找鍵key在被查找數(shù)組中，則對(duì)分查找一定可以找到key，且查找結(jié)束時(shí)變量i，j的關(guān)系一定為i≤j。②如果查找鍵key不在被查找數(shù)組中，則對(duì)分查找結(jié)束時(shí)變量i，j的關(guān)系一定為i>j，且i=j+1。③如果查找鍵key不在被查找數(shù)組中，則對(duì)分查找結(jié)束時(shí)變量i，j一定指向與key值最接近的兩個(gè)數(shù)。

● 巧用二叉樹羅列查找分支

例3.（2020.1選考真題）某對(duì)分查找算法的VB程序段如圖3所示。數(shù)組元素a（1）到a（10）的值依次為“2，3，5，8，9，10，13，17，19，20”。在文本框Text1中輸入待查找的數(shù)，執(zhí)行該程序段，則文本框Text2中顯示的內(nèi)容可能是（? ?）。

A. 9? 3

B. 9? 3? 5

C. 9? 17? 19? 13

D. 9? 3? 5? 8? 19

剖析：此題為對(duì)分查找變形程序，查找成功時(shí)沒有立即結(jié)束，一直進(jìn)行到?jīng)]有可查找區(qū)間（i>j）時(shí)結(jié)束，查找次數(shù)多。且查找鍵key值未知，查找過程不唯一，查找分支多，不適合用列表法解題。但只要畫出二叉樹模擬所有查找分支，就可快速解出此題，明確只有B選項(xiàng)符合。

點(diǎn)評(píng)：二叉樹作為一種特殊的樹形結(jié)構(gòu)，是計(jì)算機(jī)科學(xué)領(lǐng)域中一種重要的數(shù)據(jù)結(jié)構(gòu)。二叉樹的樹形結(jié)構(gòu)剛好可以模擬出對(duì)分查找過程中依次訪問到的中間位置元素，直觀形象、條理清晰。所以，當(dāng)遇到查找鍵key值未知，查找過程不唯一，需要考慮所有查找分支的試題時(shí)，用二叉樹求解尤為方便快捷，解題效率會(huì)比列表法高。

● 善用數(shù)軸分析算法思路

例4.（2018.4選考真題）數(shù)組a為一組正整數(shù)，奇數(shù)在前，偶數(shù)在后。奇數(shù)與偶數(shù)已分別按升序排序。依據(jù)對(duì)分查找思想，設(shè)計(jì)一個(gè)在數(shù)組a中查找數(shù)據(jù)Key的程序。實(shí)現(xiàn)該功能的VB程序段如圖4所示。程序中方框處可選語句為：①i=m+1，②j=m-1，③If Key

A.①、②、③? ? B.①、③、②

C.②、①、③? ? D.③、②、①

剖析：此題為對(duì)分查找算法在特殊數(shù)列中的應(yīng)用。因?yàn)楸徊檎覕?shù)據(jù)是前奇后偶的兩個(gè)升序段，且查找鍵key值未知，所以不能直接用標(biāo)準(zhǔn)對(duì)分查找程序進(jìn)行對(duì)分查找，需要根據(jù)數(shù)據(jù)的特點(diǎn)分情況討論來調(diào)整下一次的查找區(qū)間，本題可分三種情況來討論分析：

情況1：如果查找鍵key為奇數(shù)，中間位置元素a（m）為偶數(shù)[Key Mod 2=1 And a（m） Mod 2=0]。因?yàn)槠鏀?shù)在前偶數(shù)在后，所以應(yīng)調(diào)整下一次的查找區(qū)間為前半部分，即修改變量值j=m-1。

情況2：如果查找鍵key為偶數(shù)，中間位置元素a（m）為奇數(shù)[Key Mod 2=0 And a（m） Mod 2=1]。因?yàn)槠鏀?shù)在前偶數(shù)在后，所以調(diào)整下一次的查找區(qū)間為后半部分，即修改變量值i=m+1。

情況3：如果查找鍵key與中間位置元素a（m）的奇偶性一致，那么根據(jù)key值與a（m）的大小關(guān)系調(diào)整下一次的查找搜索區(qū)間。

點(diǎn)評(píng)：對(duì)分查找在特殊數(shù)列上應(yīng)用的試題，強(qiáng)調(diào)考查學(xué)生的算法思維和算法分析能力，而算法分析正是教學(xué)中的重點(diǎn)也是難點(diǎn)內(nèi)容。在算法分析過程中如果可以先使用圖表畫出數(shù)據(jù)特點(diǎn)，化抽象為具體，則可以使程序變得形象化、具體化。

本文以近幾年選考卷中的對(duì)分查找算法試題為例，總結(jié)提出了4種針對(duì)對(duì)分查找算法問題的解題策略，并分析了不同解題策略所適用的試題題型。希望學(xué)生們?cè)诿鎸?duì)對(duì)分查找類試題時(shí)，可以靈活運(yùn)用各種解題策略，迅速找到最合適的解題方法，準(zhǔn)確高效地解出題目。但是試題千變?nèi)f化，高中信息技術(shù)一線教師在平時(shí)的算法教學(xué)中，除了要讓學(xué)生掌握解題策略，提高解題能力之外，更重要的是要讓學(xué)生理解算法思想，建立算法思維，提高算法閱讀能力和分析能力，培養(yǎng)計(jì)算思維能力，將信息技術(shù)學(xué)科的核心素養(yǎng)培養(yǎng)落到實(shí)處。