找邊界,而不只是找到相等值
在已排序陣列中,找到一個相等值未必回答了真正問題。若數值出現多次,我們可能需要第一個位置、最後一次出現之後的位置,或出現次數;即使數值不存在,插入位置仍有用。
定義 12.1.1
(下界與上界)
設整數陣列 非遞減, 為整數。下界是首個滿足 的下標 ;若沒有,則 。上界是首個滿足 的下標 ;若沒有,則 。兩者均屬 : 是合法邊界,但不是陣列下標。
等於 的值恰好位於半開區間 ,數量是 。即使 不存在也成立:此時 ,區間為空。
持續記錄已知的部分
def lower_bound(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
輸入須為已排序的整數陣列,並提供隨機存取;程式不會排序或驗證輸入。每次迴圈開始時,維持
與 的關係尚未確定的元素位於 。答案邊界則仍可能是包含兩端的 中任一位置: 不在未知元素區間中,卻可以是答案。初始 時,兩段已知區域都為空,因此數值條件自然成立,無須讀取任何元素,更不用讀 。
定理 12.1.2
(下界迴圈的正確性)
設整數 (), 為整數。每次檢驗迴圈條件 時,上述不變量都成立。迴圈結束時,lower_bound(a, x) 返回 在 中的下界 。
證明
(初始化、保持不變與最後邊界)
初始時界限和兩個空區間的條件均成立。迴圈條件 保證整數中點滿足 ,所以 存在。
若 ,排序保證所有 均有 。設定 ,便擴大已知小於 的區域,不影響另一區域。否則 ,排序保證所有 都至少為 ;設定 便擴大已知至少為 的區域。兩種情況均保留界限。
終止時 。這位置之前的元素全部小於 ,從這位置開始的元素全部至少為 。若位置等於 ,後一區域為空,代表沒有元素符合條件。因此返回值恰好是定義中的下界,空陣列也成立。
證明透視
排序在哪裏被使用,以及更新為何不對稱
排序恰好被使用兩次,每個分支一次,而且只以這種形式出現:在 作一次比較,便能確定 一側的所有下標。若陣列沒有排序, 對 的 沒有任何說明。
兩個更新刻意不對稱。若 ,下標 本身已確定「小於 」,所以 可以放棄它。若 ,下標 已確定「至少為 」,但它可能正是第一個這樣的下標;因此把 設為 ,讓它仍可作為答案。
論證在未知區間 為空,即 時完結。這時兩個已確定區域恰好蓋住 ,沒有空隙也沒有重疊,而共同的邊界 就是第一個滿足 的下標。
不變量也說明:在 插入 仍保持排序。若已有相等元素,插入位置在它們之前。
命題 12.1.3
(上界與相等元素的數量)
對非遞減的整數序列, 的上界等於 的下界。等於 的元素恰好位於 中的位置,因此共有 個。
證明
(上界即下一個整數的下界)
對整數而言, 等價於 ,所以滿足其中一個條件的第一個下標,也是滿足另一個條件的第一個下標。第二個斷言:每個 都有 ,每個 都有 ,故都不等於 。當 時,由 與排序得 ,由 得 ,因此 。
概念視角組合
把邊界看成計數
在已排序的陣列中,小於 的元素構成一段前綴,因此下界恰好就是小於 的元素個數:
對 、,這三個數分別是 、、。二分搜尋不必逐一查看就能算出這個計數,因為每次比較一次就決定了一整段下標。
例題 12.1.4
(重複值給出兩個有用的邊界)
令 、。下界迴圈如下:
| lo | hi | mid | a[mid] | 操作 |
|---|---|---|---|---|
| 0 | 5 | 2 | 2 | hi = 2 |
| 0 | 2 | 1 | 2 | hi = 1 |
| 0 | 1 | 0 | 1 | lo = 1 |
結果為 。求上界時,把條件 a[mid] < x 換成 a[mid] <= x,其餘不變。區間依次為 、、、,所以 。相等元素位於位置 1、2、3,共 個。
同一陣列若 ,上下界都是 4。沒有相等值,但在位置 4 插入 3 仍保持排序。
例題 12.1.5
(邊界情況:空陣列,以及大於所有元素的值)
對空陣列,,初始區間為 ,迴圈體一次也不執行,不作任何比較便返回 。
再取 、。
| lo | hi | mid | a[mid] | 操作 |
|---|---|---|---|---|
| 0 | 3 | 1 | 3 | lo = 2 |
| 2 | 3 | 2 | 5 | lo = 3 |
兩次檢驗都有 ,所以 移到 ,迴圈在兩次比較後停止。返回值 是正確答案:沒有元素至少為 。它是邊界而不是下標, 從未被讀取。
例題 12.1.6
(用盡最多比較次數的搜尋)
令 ,,。
| lo | hi | mid | a[mid] | 操作 |
|---|---|---|---|---|
| 0 | 10 | 5 | 12 | lo = 6 |
| 6 | 10 | 8 | 18 | hi = 8 |
| 6 | 8 | 7 | 16 | hi = 7 |
| 6 | 7 | 6 | 14 | hi = 6 |
區間長度依次為 。返回 ,而 確實是第一個至少為 的元素。共作了四次比較,正好等於下文推出的界限 。
終止與成本
每次迴圈的 都在非空未知區間內。新區間是 或 ,都嚴格變短。因此非負整數 不斷減少,迴圈必定終止。
定理 12.1.7
(下界迴圈的終止與比較次數)
設某次迭代開始時,未知區間 的長度為 。迭代後其長度至多為 。因此 時迴圈至多迭代 次, 時不迭代。每次迭代作一次比較。
證明
(未知區間每次減半)
中點為 ,且 。若 變成 ,新長度為 。若 變成 ,新長度為 。設 為從長度 出發最多的迭代次數,則 ,且 時 。由歸納法, 時 : 時為 ; 時 。
由定理, 時比較次數最多為 ;空陣列不作比較。若隨機存取和整數比較均為常數時間,時間為 ,額外空間為 。這不是對必須從頭遍歷才能索引的鏈表、昂貴比較或預先排序成本的保證。
在固定寬度整數中,lo + (hi - lo) // 2 避免直接相加兩個可能很大的下標,但前提是非負界限及其差值都能由所選下標類型表示。Python 整數不會溢位;其他語言仍需選擇適當類型。
常見邊界錯誤
反例模式
把閉區間迴圈與排他的上界混用
假設程式以 hi = len(a) 開始,卻使用 while lo <= hi,中點存取保持不變。對 、,第一次比較後 lo=1;下一次迴圈會讀取超出陣列的 a[1]。 可以是答案,但不是可讀元素。
閉區間和半開區間寫法都可以正確,但初始界限、迴圈條件、更新方式和證明必須一致。只改動正確版本中的一個符號,並不會自動保留不變量。
常見錯誤
(把返回的邊界當作 存在的證明)
無論 是否出現,下界 都有定義。若 ,則 不存在;若 ,也可能 。對 、,結果是 ,但 。 存在,當且僅當 且 ,亦即 。
常見錯誤
(把上界當成最後一次出現的位置)
上界是最後一個相等元素之後的位置。對 、,上界是 ,而最後一次出現在下標 。這個公式只在 時成立;若 不存在, 可能是較小的值,而 時它根本不是下標。
練習與解答
快速檢查
(對 ,求 和 的上下界。)
按定義:第一個滿足條件的下標,若沒有則為 。
解答 · 答案
的上下界均為 ; 的上下界均為陣列長度 。兩者都不讀取哨兵元素。
快速檢查
(對 、,上下界各是多少?)
用 計算相等元素的數量。
解答 · 答案
分別為 和 ,差值 是相等元素的數量。
快速檢查
(若 ,為甚麼下界算法設定 hi = mid 而非 hi = mid - 1?)
想一想 本身會不會是答案。
解答 · 答案
中點本身可能是第一個符合位置。保留它作為未知區間的末端,可保留這個候選答案;例如 搜尋 時,首個中點是 ,但減一會令 hi=0,錯誤返回 。
快速檢查
(程式用上界條件得到 ,可以讀取 嗎?)
回想 取哪些值時才是下標。
解答 · 答案
不可以。 表示沒有元素大於 ;非空陣列的最後合法下標是 。
證明搜尋程序時,須交代答案契約、已知區域與邊界的確切處理。短小的迴圈之所以可靠,是因為每次更新都保留這些含義。