動機
二分搜尋不一定是在陣列中尋找某個鍵。有時,未知答案是一個數:容量、容許的延遲,或最大的負載。試探一個數,可以回答一個「是否可行」的問題。如果一個數可行後,所有更大的數也可行,那麼這些真假答案之間就有一條可以用二分搜尋定位的邊界。
這裏有兩項不同的證明責任。首先,必須證明判定過程確實回答了原來的可行性問題;其次,必須證明搜尋過程始終保留第一個可行值。圍繞錯誤判定進行快速搜尋,仍然會得到錯誤答案。下面以固定次序的非負負載分成連續塊為例,完整建立這兩個論證。
定義與計算模型
定義 1.3.1
(單調謂詞與邊界)
設整數 。這裏稱整數下標 上的謂詞 為單調,是指只要 ,那麼對每個 都有 。邊界 是第一個取真值的下標;若所有下標都為假,則定義 。因此 ,小於 的下標全為假,定義域中不小於 的下標全為真。
整個搜尋期間,謂詞必須固定:一次求值不能改變後續查詢的真假。實作可以從輸入計算 ,不必實際儲存一個布爾陣列。整數 是邊界哨兵,不是可以查詢 的下標。
先採用字 RAM 模型,假設下標、區間差和所需算術量都能放進常數個機器字。陣列存取和機器字上的算術為常數時間。一次 調用有自己的代價,不能自動把它當作一條機器指令。
邊界搜尋定理
定理 1.3.2
(尋找第一個真值,也容許沒有真值)
對定義在 個下標上的任意單調謂詞 ,下列算法返回邊界 。謂詞調用次數至多為 ;除謂詞自身的工作空間外,算法只需常數額外空間。
lo = 0
hi = N
while lo < hi:
mid = lo + floor((hi - lo) / 2)
if P(mid):
hi = mid
else:
lo = mid + 1
return lo
不變量記錄已經排除的區域
證明
(邊界搜尋:不變量與終止)
保持 ,以及兩項斷言:定義域中小於 的下標全為假;定義域中不小於 的下標全為真。這也等價於未知邊界滿足 。初始時,兩個外側區域都是空集,因此全假或全真的情形也滿足不變量。
若 為真,單調性說明後面的定義域下標全為真。令 保持不變量,並保留 作為可能答案。若 為假,那麼前面不可能出現真值,否則單調性會迫使 為真。因此令 也保持不變量。兩端相遇時,由 得 。
迴圈執行時,,所以每次查詢都在定義域內。非負整數寬度 嚴格減小,新寬度至多為 。經過 次迭代後,寬度至多為 。取 ,便有 ,所以寬度為零。若 ,不執行任何迭代或查詢,直接返回零。
證明透視
中點為真時,它仍可能是答案
賦值 並不是說中點錯誤,而是說嚴格位於中點之後的位置不可能是第一個真值。答案的剩餘候選是閉整數區間 ;實際查詢的中點卻位於半開下標區間 。區分這兩個角色,就能理解更新方式以及哨兵 的作用。
若每次謂詞求值至多需要 次字操作,預處理代價為 ,總時間就是 。調用次數為對數級,並不自動推出執行時間為對數級。中點寫法避免將兩個端點相加,但表示範圍仍須容納端點差及算法的其他算術結果。
可行性問題:連續負載分塊
給定非負整數 ,其中 ,並給定 。分塊由端點
描述。第 塊包含下標 的連續元素,其負載為這些元素之和。每個元素恰好出現一次,輸入次序固定,各塊非空。目標是最小化各塊負載的最大值。端點選擇只有有限種,所以最優解存在。
對整數容量 ,令 表示:存在合法分塊,使每塊負載至多為 。在容量 下可行的同一個分塊,在更大容量下仍然可行,因此 單調。這個結論來自問題定義,還不需要選定判定算法。
貪心可行性判定
從左往右掃描。只要當前塊加上下一元素仍不超容量,就加入;否則結束當前塊,用該元素另開一塊。若某個元素本身大於 ,立即拒絕,因為包含它的非負負載塊不可能滿足容量限制。
feasible(B):
blocks = 1
load = 0
for x in a, in the original order:
if x > B:
return false
if load + x > B:
blocks = blocks + 1
load = x
else:
load = load + x
return blocks <= k
這個過程不會產生空塊。尤其是第一個元素通過拒絕檢查後,一定能放進初始的空當前塊。所有實際構造出的塊都滿足容量限制,所以接受時確實可行。較難的方向是:拒絕時,不存在另一種更好的切點安排。
定理 1.3.3
(貪心判定使用最少的塊數)
若每個 ,上述貪心掃描構造的可行分塊,其塊數最少。因此 feasible(B) 返回真當且僅當 成立。
證明:比較已經到達的端點
證明
(貪心端點從不落後)
令 為貪心算法處理完第 塊後到達的端點,;掃描結束後,將後續所有 定義為 。任取另一可行分塊,其端點為 。證明對 有 。
假設 。若已經有 ,由於貪心端點不減,結論直接成立。否則,從 到 的一段,是另一分塊第 塊的後綴。元素非負,說明後綴負載不大於整塊負載,因此至多為 。
從 開始的貪心塊會延伸到最遠的可行端點:一旦加入下一項使負載超過 ,再加入更多非負項也不能恢復可行。它因而至少到達 ,完成歸納。取 ,有 ,說明貪心至多使用 塊。競爭分塊是任取的,所以貪心塊數最少。
證明透視
非負性與端點比較用在哪裏
歸納比較的是:用同樣多的塊後,貪心覆蓋的位置與任何可行分塊覆蓋的位置;它從不聲稱兩者的切點相同。非負性用了兩次。第一,競爭分塊的第 塊中,從 開始的一段是後綴,而非負元素組成的塊,其後綴負載不大於整塊,因此至多為 。第二,下一項使當前貪心負載超過 之後,再加入更多項也無法降低負載,所以貪心塊停在最遠的可行端點。假設 保證從未到末尾的位置開始的貪心塊至少含一個元素。歸納在 時收尾: 表示貪心至多用 塊,不論競爭分塊的可行塊數 是多少。若有負項,後綴性質失效;下面的反例顯示掃描會拒絕一個其實可行的容量。
搜尋最優容量
先計算
任何可行容量都不小於 ,因為含有最大元素的塊,其負載至少為該元素。容量 可行:把整個序列作為一塊即可。因此最優容量 是區間 中的整數。
用同一循環,初始化 lo = L、hi = S,並以 feasible(mid) 作為 P(mid)。初始上界已經可行,不變量為 。每條分支都由已經證明的判定支持,所以終止時返回 。無須實際查詢 。若 ,迴圈不調用謂詞,但預處理仍然需要時間。
一次可行性判定掃描 項,用 次字操作和常數工作空間。調用次數 ,所以計算上下界並搜尋的總字操作數為
最後在容量 下再掃描一次,記錄貪心切點,即得到見證分塊。這增加 時間及至多 個輸出字;搜尋本身僅需常數額外字。空間界不包含輸入陣列。
概念視角算法
把貪心測試看成沿前綴和的跳躍
設 ,這是一個非遞減陣列,。當 時,從端點 開始的貪心區塊結束於滿足 的最大 ,而測試成功當且僅當 次跳躍 能到達 。每次跳躍本身就是對單調謂詞 的邊界搜尋,所以經 預處理之後,一次測試只需 ,而不是 。
算術假設容許我們忽略甚麼
字操作界要求安全儲存 、下標,甚至可能超過當前容量的試探和 load + x。對於無界二進制輸入,不能預設這些運算都是常數時間。若每項至多有 位,則 位足以儲存這些負載、試探和及計數器。簡單二進制實作中,每次加法或比較需要 位操作,搜尋至多有 輪;包含預處理後,得到上界 。這是關於二進制輸入長度的多項式上界,並不是說位運算沒有代價。
例題
例題 1.3.4
(同時跟蹤搜尋與判定)
序列為 ,,初始 、。容量 時,貪心得到 與 ,因此令 。中點 需要 、、 三塊,所以令 。中點 可行,令 ;中點 需要三塊,令 。兩端相遇於 ,見證負載分別是 和 。最後一個不可行容量 ,結合單調性,證明更小容量都不可行。
例題 1.3.5
(重複元素也是邊界問題)
在有序陣列 中,取 為 ,第一個真值下標為一。改用 ,邊界為四。兩邊界之差三,就是元素二的出現次數。沒有元素滿足條件時,邊界為 ;它是合法返回位置,卻不是合法陣列存取下標。
例題 1.3.6
(零負載不需要正容量)
對於 與 ,有 。搜尋不調用謂詞,直接返回零;見證掃描只使用一塊 。問題容許至多兩塊。若要求恰好兩塊,還須增加一個切點,不過最優值仍為零。
常見錯誤
反例模式
負負載破壞這個貪心證明
取 、、。整個序列的負載為四,所以一塊可行。但貪心在第二個四之前結束第一塊,結果使用兩塊。容許負項後,暫時超容量的前綴可能在後面恢復可行。由分塊存在性定義的謂詞仍然對 單調,失效的是計算該謂詞的這個算法。
常見錯誤
(把連續分塊的證明用於重排後的負載)
次序也是實際假設,並不是外觀上的限制。對於 和 ,最優連續分塊的最大負載為 ,在第二項後切開即可達到。若容許重排, 與 的最大負載是 。連續分塊的證明不能直接解決任意分配問題。
常見錯誤
(把下界移到中點)
在假查詢後賦值 lo = mid 可能不終止:當上下界為零和一時,中點為零,區間可以完全不變。為假的中點已被排除,所以正確的更新是 lo = mid + 1。
常見錯誤
(對非單調謂詞做搜尋)
迴圈每一輪也許都會終止,卻仍可能丟棄答案。對真假序列 [true, false, true],算法首先查詢中間項,得到假並令 ;隨後返回 ,但第一個真值其實是 。單調性正是每個被丟棄區域的依據。
總結
邊界搜尋之所以正確,是因為固定的單調謂詞為每次排除區域提供依據。將最優化轉成可行性問題,還需要證明判定過程本身。對於非負連續負載,貪心端點比較完成這一證明;二分搜尋隨後通過對數次線性掃描,找到最優容量。
練習
快速檢查
(跟蹤 [false, false, false] 上的邊界搜尋。若三項全真,結果如何?解釋空定義域的情況。)
解答 · 答案
從 開始。下標一為假,得到 ;下標二為假,得到 ,返回哨兵三。若全真,查詢一和零後依次得到 、,返回零。若 ,直接跳過迴圈,邊界同樣為零。這些情況都不需要定義域外的查詢。
快速檢查
(用兩次邊界搜尋計算有序陣列中目標 的出現次數,包含目標不存在的情況。)
解答 · 答案
求 為第一個滿足 的下標,求 為第一個滿足 的下標;相應謂詞全假時返回 。有序性保證兩個謂詞都單調。恰好是 中的元素等於 ,所以出現次數為 。目標不存在時,兩邊界相等,也容許它們都等於 。
練習 1.3.7
(對 、 求最優容量。給出可行分塊,並證明更小容量不可能。)
核心
解答(3)
- 1
從下方限制容量
任何可行容量都不小於 。
依據: 含有元素 的塊,其負載至少為 。
- 2
在容量 下給出分塊
關鍵一步
連續塊 、、 的負載為 、、,都不超過 ,且共有三塊,所以 成立。
- 3
得出最優容量為
容量 可行,更小的容量都不可行,因此 。這個證書不必再列完整的搜尋過程。
快速檢查
(指出貪心證明的哪些具體步驟使用了非負性。為甚麼僅有 的單調性不足以證明掃描正確?)
解答 · 答案
從一個塊中刪去前面的非負元素後,後綴負載不大於整塊;另外,加入下一項導致超容量後,繼續加入非負項不可能降低總和。這兩點都使用非負性。存在性謂詞的單調性只支持尋找它的邊界,並不保證任意候選判定程式都能計算它。負項反例區分了這兩件事。
練習 1.3.8
(當 時,證明恰好分成 個非空塊,與至多分成 塊具有相同最優容量。 時有甚麼問題?)
核心證明
解答(3)
- 1
從使用 塊的可行分塊出發
因 ,至少有一塊包含兩個元素。
- 2
把該塊分成兩個連續的非空部分
關鍵一步
新分塊有 塊,容量界不變。重複直到恰好有 塊。
依據: 元素非負,每個新塊的負載都不超過原塊的負載。
- 3
比較兩個最優值
∎恰好 塊的分塊也是至多 塊的分塊;上面的拆分又在不提高容量下給出相反方向,所以兩個最優值相同。若 ,恰好 個非空塊不可能,但至多 塊仍然可行。
快速檢查
(若可行性判定每次需要 時間,進行 次調用的二分搜尋是否只需 時間?給出包含預處理代價 的合理上界。)
解答 · 答案
必須計入每次調用的實際代價和迴圈開銷。對於 ,在題設的每次調用代價與字操作假設下,上界為 。調用次數是對數級,不代表調用內部消耗的時間也是如此。若搜尋範圍可能只有零或一個候選,可用 並保留常數開銷。