| “Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…” — Donald Knuth
每個大學生都可以在抽象上跟你解釋二分法的概念，但是一旦需要寫出正確無誤、考量到邊界條件的實作，大概只有10%左右的工程師能夠做到。儘管現代工具非常方便，只要呼叫bisect，就可以把一串有序列表二分搜尋。但學習正確地寫出二分法，對於鍛鍊程式思維還是非常有幫助。
常見的二分問題
大多數的二分問題，基本上可以被視為等價於下列三種問題
- 尋找第一個滿足條件的目標
- 尋找最後一個滿足條件的目標
- 只要滿足目標就好，在哪裡不重要
我們可以來看些例子幫助理解。給定一個有序列表
|
1 2 |
value: [1, 1, 1, 2, 2, 2, 2, 3, 3] # index: [0 ,1, 2, 3, 4, 5, 6, 7, 8] |
大體上可以分成
- 尋找第一個出現的2
- 尋找最後一個出現的2
- 尋找比2大的第一個數
- 尋找比2小的最後一個數
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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的範圍。
- while left <= right
- while left < right
- while left + 1 < right
while left <= right 尋找第一個滿足條件的元素
題目是給定一個list, 如果有找到元素則回傳第一個元素出現的位置, 若無則回傳-1。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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 + 1 和 right = mid - 1 有一個很棒的特性，迴圈每次執行時，範圍都會縮小，想像下列情況。O 代表該元素符合條件, X代表該元素不符合條件。m代表L與R的中點。
- 若符合條件, 則right =mid - 1
- 若不符合條件, 則left = mid + 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
[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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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，不斷二分後必然會進入最後三種情況
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# 假定 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 的情況
|
1 2 3 4 5 6 7 8 |
# 假定 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。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# 假定 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 尋找第一個滿足條件的元素
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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都會讓區間縮小到0~1或1~2，並離開迴圈。
至於 n >= 3以上的元素，想當然爾都能夠縮小區間範圍。
每次更新區間範圍時，解必然被包含在內
|
1 2 3 4 |
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 <= right 和 left < right等等。我認為loop invariant是很重要的觀念，但是用開區間、閉區間闡述實在有點先射箭、再畫靶的味道，二分法的程式碼其實很緊湊，每一行之所以這樣寫，背後都有兩個以上的因素去影響著。迴圈的條件會影響 left right範圍的初始化，而left/right的更新方式也受到取用mid和迴圈條件的定義、離開迴圈後要不要再做越界檢查或滿足性檢查，又是另一個課題。本文中不談開區間、閉區間，而是用範例說明在邊界條件會發生的狀況，希望這篇文章能讓讀者更理解二分法背後的思考脈絡，讓自己的程式思維變得更加清晰易懂。