前言

Binary search 是針對已排序的 array，搜尋特定的 key value，是一個簡單且好用的搜尋法，會不斷將搜尋區域切一半，減少搜尋時間，時間複雜度是 O(logN)

概念

根據key value跟中值比對後的結果，決定要往哪一半搜尋

  • 如果比中值小，那就是往左半部繼續搜尋
  • 如果比中值大，就是往右半部繼續
  • 如果一樣就是找到了

大概步驟如下

  1. 得到已排序陣列的中值
  2. 比對 key value 與中值的大小
  3. 如果 key value < 中值或 > 中值，搜尋範圍減少一半，往可能的那一半繼續上述的步驟

pseudo code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 遞迴作法
BinarySearch(A[1..n], left, right, key)

if left > right
　return 

mid ← (left + right) / 2

if key = A[mid]
　return mid

else if key < A[mid]
  return BinarySearch(A, left, mid-1, key)

else 
  return BinarySearch(A, mid+1, right, key)
1
2
3
4
5
6
7
8
9
10
11
// 迴圈作法
BinarySearch(A[1..n], left, right, key)

while left <= right:
　mid ← (left + right) / 2 
  if key = A[mid]
    return mid
  else if key < A[mid]
    right = mid - 1
  else 
    left = mid + 1