Binary Search Algorithm
Binary Search 是在已經排序好的數列裡去找一個數字的演算法,舉例來說在[1, 2, 3, 4, 5] 找出 4 是否存在這個數列當中,並且回傳index
def binary_search(array, target):
lo = 0
hi = len(array) - 1 #[Round1][Round2]
while lo <= hi: # true true
mid = (lo + hi) // 2 # 2 3
if array[mid] == target: # false true
return mid # return
elif array[mid] > target: # false
hi = mid - 1
else: # true
lo = mid + 1 # 3
return -1相信大家對演算法都很熟悉,但實際上在寫code的時候有很多boundry case 需要考慮,尤其是while loop 一不小心就很可能無窮迴圈了。例如:
while lo <= hi: # 如果寫成 < 會少考慮到最後一個element
hi = mid - 1 # 如果忘了 -1 或是 +1 會變成無窮迴圈
lo = mid + 1Binary Search in Array with Duplicate
當數列中有重複的數字的時候,[1, 2, 3, 4, 4, 4, 4, 4, 5],上面的code會回傳target 的任一個index,有些情形下我們必須回傳target的第一個index或者是最後一個index
def binary_search_first(array, target):
lo = 0
hi = len(array) - 1
while lo <= hi:
mid = (lo + hi) // 2
if array[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return lodef binary_search_last(array, target):
lo = 0
hi = len(array) - 1
while lo <= hi:
mid = (lo + hi) // 2
if array[mid] <= target:
lo = mid + 1
else:
hi = mid - 1
return lo - 1
心法
if array[mid] < target # lo會是第一個不滿足 < target
lo = mid + 1 # 也就是 target <= array[lo]
if array[mid] <= target # lo會是第一個不滿足 <= target
lo = mid + 1 # 也就是 target < array[lo]這邊我的重點只要注意 lo 就好,因為最後也是return lo。在 binary_search_first 裡
if array[mid] < target:
lo = mid + 1
else: #array[mid] >= target
hi = mid - 1這個條件代表説 mid 還沒走到target 所以 lo 可以再從mid 再加一步,但是當mid走到target的時候,就必須把hi 從mid 退一步。
但這時候會擔心一件事情,如果這時候的mid 已經是 first index的話不就錯了嗎? 例如說 [1, 2, 3, 4, 4, 4, 4, 4, 5],mid = 3,如果退一步則 hi = 2 感覺會出問題!
神奇的是這個 hi 就不會再被更新了,因為mid < hi → array[mid] < target。所以現在只有lo 會一直往前走,直到lo == hi,進入while lo ≤ hi 的最後
lo == hi # lo == hi == 2
mid = (lo + hi) // 2 # mid = lo
if array[mid] < target: # true
lo = mid + 1 # lo = lo + 1
return lo # lo == 3Find Rank
有時候問題是 find the number of element < target 或是 find the number of element ≤ target 這樣的問題其實跟上面find first/last index是一模一樣的
(*只差 return lo -1 這步改成 return lo)
def count_less(array, target):
lo = 0
hi = len(array) - 1
while lo <= hi:
mid = (lo + hi) // 2
if array[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return lodef count_less_or_equal(array, target):
lo = 0
hi = len(array) - 1
while lo <= hi:
mid = (lo + hi) // 2
if array[mid] <= target:
lo = mid + 1
else:
hi = mid - 1
return lo
Summary
array[mid] == target # 如果只需要找到任意一個index遇到==就可return array[mid] < target # lo會是第一個不滿足 < target
# 也就是 target <= array[lo]
# lo is number of element < target
array[mid] <= target # lo會是第一個不滿足 <= target
# 也就是 target < array[lo]
# lo is number of element <= targetBinary search 說起來很簡單,但是有很多需要小心的地方,一些boundry condition的不同就會造成截然不同的結果。每次寫之前要想清楚,多寫幾次應該就可以體會了!