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

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