Binary Search

發表於 Disqus：
文章字數： 1k 所需閱讀時間 ≈ 2 分鐘

Binary search 是一個用在已排序數列( sorted list )上有效率的演算法。 藉由不斷把 list 分割一半直到最後將可能的位置縮小到一個。 以下是 binary search step-by-step 的描述：

  1. Let min = 1 and max = n
  2. (max+min)/2且round成整數
  3. 如果猜中了，就停止
  4. 如果太小，則把min設成guess+1
  5. 如果太大，則把max設成guess-1
  6. 重新從第二步驟開始

完整程式碼

時間複雜度： O(logN) 

data = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def binary_search(data, key):
    #設置選取範圍的指標
    low = 0
    upper = len(data) - 1
    while low <= upper:
        mid = (low + upper) / 2  #取中間索引的值
        if data[mid] < key:    #若搜尋值比中間的值大，將中間索引+1，取右半
            low = mid + 1
        elif data[mid] > key:  #若搜尋值比中間的值小，將中間索引+1，取左半
            upper = mid - 1
        else:                    #若搜尋值等於中間的值，則回傳
            return mid
    return -1


index = binary_search(data, 5)
if index >= 0:
    print("找到數值於索引 " + str(index))
else:
    print("找不到數值")
# 時間複雜度 ## worst case

剛好分割到最後一個數。

  1. 假設 n 為 2 的指數( n = 128 )，則需要 8 次( +1 )
  2. 假設 n 不為 2 的指數( n = 1000 )，則需要 10 次(round( )+1 )

best case

第一個就找到:

practice

You have an array containing the prime numbers from 2 to 311 in sorted order: [2, 3, 5, 7, 11, 13, ..., 307, 311]. There are 64 items in the array. About how many items of the array would binary search have to examine before concluding that 52 is not in the array, and therefore not prime?

7

參考資料