Skip to main content

二分法的邊界條件

Opass
A life well lived

“Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…” — Donald Knuth

每個大學生都可以在抽象上跟你解釋二分法的概念,但是一旦需要寫出正確無誤、考量到邊界條件的實作,大概只有10%左右的工程師能夠做到。儘管現代工具非常方便,只要呼叫bisect,就可以把一串有序列表二分搜尋。但學習正確地寫出二分法,對於鍛鍊程式思維還是非常有幫助。

大多數的二分問題,基本上可以被視為等價於下列三種問題

  • 尋找第一個滿足條件的目標
  • 尋找最後一個滿足條件的目標
  • 只要滿足目標就好,在哪裡不重要

我們可以來看些例子幫助理解。給定一個有序列表

  value: [1, 1, 1, 2, 2, 2, 2, 3, 3]
# index: [0 ,1, 2, 3, 4, 5, 6, 7, 8]

大體上可以分成

  • 尋找第一個出現的2
  • 尋找最後一個出現的2
  • 尋找比2大的第一個數
  • 尋找比2小的最後一個數
  value: [1, 1, 1, 2, 2, 2, 2, 3, 3]
# 尋找第一個出現的2 = 尋找滿足 x >= 2 的第一個x
# [X, X, X, O, O, O, O, O, O]
# ↑

value: [1, 1, 1, 2, 2, 2, 2, 3, 3]
# 尋找找最後一個出現的2 = 尋找滿足 x <= 2 的最後一個數
# [O, O, O, O, O, O, O, X, X]
# ↑

value: [1, 1, 1, 2, 2, 2, 2, 3, 3]
# 尋找 > 2 的第一個數
# [X, X, X, X, X, X, X, O, O]
# ↑

value: [1, 1, 1, 2, 2, 2, 2, 3, 3]
# 尋找 < 2 的最後一個數
# [O, O, O, X, X, X, X, X, X]
# ↑

因此我們可以把大多數的二分法的問題抽象成,給定一個檢定函數,尋找(第一個/最後一個)滿足檢定函數的目標。這裡的檢定函數就是一個檢查元素是O還是X的函數。

常見的二分法寫法

常見的二分法寫法有三種,最大的不同是while條件的定義與lower_bound, upper_bound的範圍。

1. while left <= right
2. while left < right
3. while left + 1 < right

while left <= right 尋找第一個滿足條件的元素

題目是給定一個list, 如果有找到元素則回傳第一個元素出現的位置, 若無則回傳-1。

def findFirstPosition(self, nums, target):
left = 0
right = len(nums) - 1

while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
if left >= len(nums) or nums[left] != target:
return -1
return left

要保證程式碼行為正確無誤,靠的不是鳴人的相信我之術,而是周全的思考每一個邊界條件。

這個寫法的 Loop Invariance 是 left <= right ,加上初始化的區間是0 ~ n-1,代表left, right可能的範圍是0 <= n - 1最後一路縮小到 x <= x, 最後離開迴圈。

每次執行時區間必會縮小

left = mid + 1right = mid - 1 有一個很棒的特性,迴圈每次執行時,範圍都會縮小,想像下列情況。O 代表該元素符合條件, X代表該元素不符合條件。m代表L與R的中點。

  • 若符合條件, 則 right = mid - 1
  • 若不符合條件, 則 left = mid + 1
    [O,  O]
# [Lm, R]
# R[L, ] => L停在第一個滿足條件的位置

[X, O]
# [Lm, R]
# [ LRm] => 歸納成[O]

[X, X]
# [Lm R]
# [ LR] => 歸納成[X]]

[O]
# [LRm]
# R[L] => L沒有越界,代表有元素滿足條件

[X]
# [LRm]
# [R]L => L越界, 代表沒有任何元素滿足條件

我們只探討2個元素以下的可能, 原因是對於三個以上的元素, 最後都會收縮歸納成2個以下的元素。

每次迴圈改變區間範圍時,解必然在其中或是區間外的右邊

假定解存在, 我們觀察一下, 如果middle所檢定的元素不是解, 代表解只可能出現在mid之右。因此把left移動到mid之右,確保左邊界移動後,解會在[left, right]區間內。

而如果middle檢定的元素是解,代表解已經存在, 但可能有更好的解,因為我們追求的是最左邊的解。當我們把right = mid - 1時,代表我們想看看right的左邊有沒有更好的解。如果有的話就重複找解的過程,如果新的區間都沒有解,left最後也會移動到right的右邊,也就是解的位置。

假定解不存在,那就會發生left不斷往右移動,最後和右邊界重疊,接著移動到右邊界之右並離開迴圈。此時left已經out of index, 因此需要在離開迴圈時檢查 if left >= len(nums)

最後必然離開迴圈

right = mid - 1, left = mid + 1 確保了left, right位於同一個位置後, 下一輪迴圈會順利中止,因為右邊界會跑到左邊(或是左邊界會跑到右邊)

歸納

  • 每次執行時區間必會縮小
  • 每次迴圈改變區間範圍時,解必然在其中或是區間外的右邊
  • 最後必然離開迴圈

而離開迴圈後, L恰好會落在區間外側之右,因此檢查L是否出界,若不出界則L就是滿足檢定函數的解。

但滿足檢定函數並不代表滿足題意,題目要求的是「尋找第一個出現的target」, 而我們的檢定函式做的是尋找第一個滿足 x >= target 的數,有可能x都不是target,所以得做一個額外的判斷 or nums[left] != target

while left < right 尋找第一個滿足條件的元素

Talk is cheap, show me the code

def findFirstPosition(self, nums, target):
left = 0
right = len(nums)

while left < right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
if left >= len(nums) or nums[left] != target:
return -1
return left

這次的寫法和剛剛的不太一樣,我們可以發現

  • 迴圈條件改成 left < right
  • right 涵蓋了 n 而不是 n - 1
  • right 的更新改成 mid 而不是 mid - 1

每次執行時區間必會縮小,且必然能夠結束迴圈

(left + right) // 2 會讓中點偏左。中點絕對不會出現在right。因此right = mid必然會讓區間縮小。left = mid + 1 也必然會讓區間縮小。直到最後left == right離開迴圈為止。

每次迴圈改變區間範圍時,解必然在其中,若無解,則區間最後會向右越界

我們像剛才一樣, 對這種寫法做分析,我們先假設陣列長度 >=2,不斷二分後必然會進入最後三種情況

# 假定 left = 0, right = 2 (right初始化成n)
[X, X]
# [L m] R
# [ ] LR L越界且無解

[X, O]
# [L m R]
# [Lm R]
# [ LR] L停在第一個滿足條件的位置

[O, O]
# [L m R]
# [Lm R]
# [LR ] L停在第一個滿足條件的位置

我們再看看陣列長度為 1 的情況

# 假定 left = 0, right = 1 (right初始化成n)
[X]
# [Lm] R
# [ ] LR 解不存在, L停在右側(且越界)

[O]
# [Lm] R
# [LR] L停在解的位置

如果陣列長度為0,left/right index都會越界,解也不存在。因此歸納上述,只要越界,解就不存在,反之left在離開迴圈後會停在第一個解的位置。

這個原因也不難想像,每次會迴圈進行讓區間變小時,若 mid 為解,則 right = mid 會讓解的範圍往左靠,使 right 涵蓋到解。若 mid 不為解,則 left 會往 mid + 1 縮小,使 left 涵蓋在解可能出現的地方之中。當 left == right 時離開迴圈。若有解則left必然停留在其上,若無解則left必然會移動到right的位置(也就是最右側)。

為什麼初始化不寫成 right = n - 1?

我們可以探討一下為何不寫成 right = n - 1。

# 假定 left = 0, right = 1 (right初始化成n - 1)
[X, X]
# [Lm R]
# [ LR] L在界內但L並沒有滿足條件

[X, O]
# [Lm R]
# [ LR] L停在第一個滿足條件的位置

[O, O]
# [Lm R]
# [LR ] L停在第一個滿足條件的位置

# 假定 left = 0, right = 0 (right初始化成n - 1)
[O]
# [LR] 根本不會進入迴圈,還是得檢查該位置是否有解。

[X]
# [LR] 根本不會進入迴圈,還是得檢查該位置是否有解

會發生L沒有越界,但是L依然沒有滿足條件,因此離開迴圈後,還是得多花一步檢查L的位置是否滿足。不會讓事情變得比較簡單。

nums[left] != target的目的

而 nums[left] != target,其實也是因為滿足 x >= target的元素並不保證 x == target,因為題目的目標是尋找target,才要加入這一行檢查。當然你可以用這一行檢查順便解決 right = n - 1 離開迴圈後沒有檢查到left位置元素的問題。但兩者的目的不太相同,混在一起容易讓思考不清楚。

歸納

  • 每次執行時區間必會縮小,且必然能夠結束迴圈
  • 每次迴圈改變區間範圍時,解必然在其中,若無解,則區間最後會向右越界

因此這種寫法也能夠順利找到target的FirstPosition

while left + 1 < right 尋找第一個滿足條件的元素

def findFirstPosition(self, nums, target):
if len(nums) == 0:
return -1
left = 0
right = len(nums) - 1

while left + 1 < right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid
else:
left = mid

if nums[left] == target:
return left
if nums[right] == target:
return right
return -1

這種寫法有其優點和缺點。while 條件是 left + 1 < right,代表left, right兩者相鄰時就會離開迴圈。因此我們只要確保每次進入離開迴圈,範圍會縮小到剩下2個元素即可。

每次執行時區間必會縮小,且必然能夠結束迴圈

(left + right) // 2 會讓中點偏左。假設n = 3, Left = 0, right = 2, 其中點為1,left = mid或right = mid都會讓區間縮小到01或12,並離開迴圈。

至於 n >= 3以上的元素,想當然爾都能夠縮小區間範圍。

每次更新區間範圍時,解必然被包含在內

if nums[mid] >= target:
right = mid
else:
left = mid

因為有解的時候 right = mid,所以如果解存在,則解必然會在區間內。而且解區間會刻意往左縮小,試圖涵蓋住最左邊滿足條件的元素。

離開迴圈之後

綜合以上兩點,離開迴圈後,left, right必然包住解,因此我們只要先看看left是不是解,若不是解,再看看right是不是解,就可以知道第一個滿足條件的index。

記得要優先檢查 index range,因為可能一開始left/right就out of index。

評論

這種寫法的優點在於,和其他寫法有相同的時間複雜度,但不用費太多心思思考更新區間+1 -1的問題。反正一律讓right = mid或left = mid就可以了。

但如果我們能夠確保解必然存在在陣列之中,那麼第一種、第二種寫法都能夠省略去離開迴圈後的檢查,因為離開迴圈後 left 必然停留在解上,直接回傳即可。但這種寫法在離開迴圈後,還是得多寫兩行檢查 left/right,判斷哪一個才是解。

結論

有些文章會引用開區間、閉區間、loop invariant的觀念來闡述 left <= rightleft < right等等。我認為loop invariant是很重要的觀念,但是用開區間、閉區間闡述實在有點先射箭、再畫靶的味道,二分法的程式碼其實很緊湊,每一行之所以這樣寫,背後都有兩個以上的因素去影響著。迴圈的條件會影響 left right範圍的初始化,而left/right的更新方式也受到取用mid和迴圈條件的定義、離開迴圈後要不要再做越界檢查或滿足性檢查,又是另一個課題。本文中不談開區間、閉區間,而是用範例說明在邊界條件會發生的狀況,希望這篇文章能讓讀者更理解二分法背後的思考脈絡,讓自己的程式思維變得更加清晰易懂。