iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 16
1
Software Development

30天學演算法和資料結構系列 第 16

[演算法] 二分搜尋 (Binary Search)

  • 分享至 

  • xImage
  •  

還記得之前討論過的樹嗎?都會分成左子樹和右子樹,而二分搜尋也是遵循這樣的邏輯來運算的。

二分搜尋 (Binary Search) 是取 已排序資料的中間索引的值,來確認是否為要搜尋的數,若不是,則將資料以中間索引分為兩半。此時便比較待搜尋的值與中間索引的值的大小,若比較小,則選擇較小的那一半資料,反之亦然。接著再繼續從一半的資料中取中間索引的值做比較,重複以上的步驟,直到找到為止。

直接來看程式碼吧。

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("找不到數值")

上一篇
[演算法] 循序搜尋 (Sequential Search)
下一篇
[演算法] 插補搜尋 (Interpolation Search)
系列文
30天學演算法和資料結構31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

1
showlin
iT邦新手 5 級 ‧ 2019-09-10 17:11:05

不好意思,請問一下number是不是沒有定義,還是少一個參數引入?謝謝

ramonliao iT邦新手 5 級 ‧ 2019-09-12 09:36:28 檢舉

已更正,謝謝

0
1092B0007
iT邦新手 3 級 ‧ 2021-04-23 18:55:08

好欸

我要留言

立即登入留言