淺談二分策略的應用

淺談二分策略的應用二分策略來源一個很簡單的想法——在最壞情況下排除盡可能多的干擾，以盡可能快地求得目標效率高！對信息的充分利用，盡可能去除冗余，減少了不必要計算

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

——應用于一般有序序列

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

——應用于一般有序序列

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

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

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

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

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

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

——應用于退化了的有序序列

與類型一中的二分查找相比，最大的區(qū)別在于這里的二分在判斷選擇哪一個部分遞歸調(diào)用時沒有了比較運算*。顯式有序序列隱含的退化了的有序序列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）—

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

現(xiàn)在觀眾們想知道，哪頭奶牛是所有可能成為冠軍的牛中排名最靠后的。并要求你列舉出一個可能的比賽安排使該奶牛獲勝。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，能否很快構造出對戰(zhàn)方式？可以證明這樣貪心是正確的。如果利用靜態(tài)排序二叉樹，整個問題可以在O(Nlog2N)時間完成。例如N=8，K=2，X=66

75

34

82

16

54

26

4可以！1/16/202515小結算法的根本——在一個隱含的退化了的有序序列中進行二 分查找

00000000111111

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

——應用于無序序列

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

A2

…

Ai，我們希望再加入點i+1，將其變成長度為i的線路。A1A2A3Aii+1i+11/16/202521進一步分析這樣的詢問會不會問到底也沒法插入i+1？不會！因為i+1有邊到Ai。由此，我們得到了一種詢問方法，但最壞情況下總的詢問次數(shù)可能是O(N2)的。i+1i+1A1A2A3Ai1/16/202522二分搜索的使用由于對每個點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小結算法的根本—— 在一個無序的01序列中進行二分查找 001011100111我們所尋找的—— 一個特殊的子串‘01’011/16/202524小結由此可見，這樣的二分搜索方法往往應用于那些可行解較多，但需要高效地構造一組可行解的問題。i+1i+1A1A[i/2]Aii+1OP?1/16/202525總結在這里我僅簡單地介紹了三個二分策略應用的例子，要涵蓋二分策略的所有應用甚至是大部分應用都是困難的。這里我想指出的是：二分思想雖然簡單，但是它的內(nèi)容還是非常豐富的。我們不能讓二分思