淺談二分策略的應(yīng)用

淺談二分策略的應(yīng)用二分策略來源一個(gè)很簡(jiǎn)單的想法——在最壞情況下排除盡可能多的干擾，以盡可能快地求得目標(biāo)效率高！對(duì)信息的充分利用，盡可能去除冗余，減少了不必要計(jì)算

1/16/20252三種應(yīng)用類型類型一：二分查找 ——應(yīng)用于一般有序序列類型二：二分枚舉 ——應(yīng)用于退化了的有序序列類型三：二分搜索 ——應(yīng)用于無序序列1/16/20253類型一：二分查找

——應(yīng)用于一般有序序列

申明：“有序序列”，僅包含兩層意思：第一，它是一個(gè)序列，一維的第二，該序列是有序的，即序列中的任意兩個(gè)元 素都是可以比較的，也就是擁有我們平時(shí) 所說的全序關(guān)系1/16/20254類型一：二分查找

——應(yīng)用于一般有序序列

二分查找的一般實(shí)現(xiàn)過程：（1）確定查找范圍（2）選擇基準(zhǔn)元素（3）關(guān)鍵字比較，確定更精確的范圍（4）判斷結(jié)果，如不夠精確，轉(zhuǎn)至（2）1/16/20255例一：順序統(tǒng)計(jì)問題[問題描述]

給定一個(gè)由n個(gè)不同的數(shù)組成的集合S，求其中第i小的元素。例如： S={3,7,2,6,8,1,5}，i=4 Answer=51/16/20256問題的一般解法二分查找的過程：（1）確定待查找元素在S中（2）在n個(gè)元素中隨機(jī)取出一個(gè)記為x，將x作基準(zhǔn)（3）設(shè)S中比元素x小的有p個(gè)

（4）如果找出x，輸出；否則轉(zhuǎn)至（2）因?yàn)閤是隨機(jī)選出的，由簡(jiǎn)單的概率分析，可得算法的復(fù)雜度期望值為O(n)。

如果i<p，我們將范圍確定為S中比x小的元素，求該范圍內(nèi)第i個(gè)元素；如果i=p，表示第i小的元素就是x

如果i>p，我們將范圍確定為S中比x大的元素，求該范圍內(nèi)第i-p-1個(gè)元素；1/16/20257小結(jié)舉這個(gè)例子，是想說明兩點(diǎn)：第一，二分查找==

logn第二，二分查找==平均??1/16/20258類型二：二分枚舉

——應(yīng)用于退化了的有序序列

與類型一中的二分查找相比，最大的區(qū)別在于這里的二分在判斷選擇哪一個(gè)部分遞歸調(diào)用時(shí)沒有了比較運(yùn)算*。顯式有序序列隱含的退化了的有序序列1/16/20259例二：BTP職業(yè)網(wǎng)球賽[問題描述]N（N≤65536）—

有N頭奶牛（N是2P）參加網(wǎng)球淘汰賽。即N頭奶牛分成N/2組，每組兩頭奶牛比賽，決出N/2位勝者；所有勝者繼而分成N/4組比賽……直至剩下一頭牛是冠軍。K（1≤K≤N-1）—

比賽既要講求實(shí)力，又要考慮到運(yùn)氣。每頭奶牛都有一個(gè)BTP排名，恰為1－N。如果兩頭奶牛的排名相差大于給定整數(shù)K，則排名靠前的奶?？偸勤A排名靠后的奶牛；否則，雙方都有可能獲勝。Answer—

現(xiàn)在觀眾們想知道，哪頭奶牛是所有可能成為冠軍的牛中排名最靠后的。并要求你列舉出一個(gè)可能的比賽安排使該奶牛獲勝。1/16/202510初步分析由于N很大，猜想可以通過貪心方法解決。

K+11

K+22 ……

2KK

3K+12K+1 …… ……1/16/202511初步分析但我們很容易找到反例，例如：N=8,K=2但最優(yōu)解為6。解決方法：枚舉！3

14

27

58

64

38

74

8圖BTP-16

75

34

82

16

54

26

4圖BTP-21/16/202512性質(zhì)：隱含的有序性如果排名為X的選手最終獲勝，那么排名在X前的選手Y也可以獲勝。證明：情況一：Y被Z≠X擊敗

Z?…Y?…X?Z…?… ? …?YXXXYYYX1/16/202513性質(zhì)：隱含的有序性如果排名為X的選手最終獲勝，那么排名在X前的選手Y也可以獲勝。證明：情況二：Y被X擊敗Y?…X?… …… ? …?XXYXYYYX1/16/202514問題的解決于是，我們可以二分枚舉獲勝的X。知道了X，能否很快構(gòu)造出對(duì)戰(zhàn)方式？可以證明這樣貪心是正確的。如果利用靜態(tài)排序二叉樹，整個(gè)問題可以在O(Nlog2N)時(shí)間完成。例如N=8，K=2，X=66

75

34

82

16

54

26

4可以！1/16/202515小結(jié)算法的根本——在一個(gè)隱含的退化了的有序序列中進(jìn)行二 分查找

00000000111111

X<Ans X≥Ans我們所尋找的—— 兩種值的分界點(diǎn)。11/16/202516小結(jié)應(yīng)用這類二分枚舉的最優(yōu)性問題近來很是熱門（如NOI2003樹的劃分），而且這類試題很容易誘導(dǎo)選手直接采用動(dòng)態(tài)規(guī)劃或是貪心算法，而走入死胡同。所以，今后我們?cè)诳紤]最優(yōu)性問題時(shí)，應(yīng)當(dāng)注意問題是否隱含了一個(gè)有序的01序列，它是否可以用二分枚舉將最優(yōu)性問題轉(zhuǎn)化為可行性問題。切記！“退一步海闊天空”。1/16/202517類型三：二分搜索

——應(yīng)用于無序序列

二分策略有序序列無序序列1/16/202518例三：推銷員的旅行[問題轉(zhuǎn)述]這是一個(gè)交互式問題：在一個(gè)未知的競(jìng)賽圖（即有N頂點(diǎn)，兩點(diǎn)間恰只含一條邊的有向圖）中，通過不斷詢問任意兩點(diǎn)之間邊的方向，尋找一條哈密爾頓路。目標(biāo)是詢問次數(shù)盡可能少。思考...1/16/202519初步分析為了避免詢問的盲目性，我們嘗試使用增量法逐步擴(kuò)展序列。我們先任意詢問兩個(gè)點(diǎn)不妨設(shè)詢問結(jié)果是1到2有邊，于是，我們就得到一條長(zhǎng)度為1的線路。121/16/202520初步分析假設(shè)我們已設(shè)計(jì)了一條含有前i個(gè)點(diǎn)、長(zhǎng)度為i-1的線路A1

A2

…

Ai，我們希望再加入點(diǎn)i+1，將其變成長(zhǎng)度為i的線路。A1A2A3Aii+1i+11/16/202521進(jìn)一步分析這樣的詢問會(huì)不會(huì)問到底也沒法插入i+1？不會(huì)！因?yàn)閕+1有邊到Ai。由此，我們得到了一種詢問方法，但最壞情況下總的詢問次數(shù)可能是O(N2)的。i+1i+1A1A2A3Ai1/16/202522二分搜索的使用由于對(duì)每個(gè)點(diǎn)Ak(1≤k≤i)，要么Ak

i+1，要么i+1

Ak。且已知A1

i+1，i+1

Ai。因此，我們可以用二分搜索來尋找Ak，使i+1可以插入Ak與Ak+1之間。這樣，我們所需要的詢問次數(shù)僅為O(nlogn)。i+1i+1A1A[i/2]Aii+11/16/202523小結(jié)算法的根本—— 在一個(gè)無序的01序列中進(jìn)行二分查找 001011100111我們所尋找的—— 一個(gè)特殊的子串‘01’011/16/202524小結(jié)由此可見，這樣的二分搜索方法往往應(yīng)用于那些可行解較多，但需要高效地構(gòu)造一組可行解的問題。i+1i+1A1A[i/2]Aii+1OP?1/16/202525總結(jié)在這里我僅簡(jiǎn)單地介紹了三個(gè)二分策略應(yīng)用的例子，要涵蓋二分策略的所有應(yīng)用甚至是大部分應(yīng)用都是困難的。這里我想指出的是：二分思想雖然簡(jiǎn)單，但是它的內(nèi)容還是非常豐富的。我們不能讓二分思