Binary Search Algorithm

MingFong Jhang
Sep 1, 2018 · 5 min read

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 + 1

Binary 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 lo
def 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 == 3

Find 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 lo
def 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 <= target

Binary search 說起來很簡單,但是有很多需要小心的地方,一些boundry condition的不同就會造成截然不同的結果。每次寫之前要想清楚,多寫幾次應該就可以體會了!

MingFong Jhang

Written by

菜鳥工程師

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade