1. 二分搜索是什么？

二分搜索（英語：binary search），也叫折半搜索（英語：half-interval search），是一種在有序數(shù)組中查找特定元素的搜索算法。所以是用二分查找的前提是數(shù)組必須是有序的；時間復(fù)雜度，空間復(fù)雜度請參照下圖；有的同學(xué)可能對時間復(fù)雜度和空間復(fù)雜的計算有點繞，我又在其他文章中介紹；

圖片來自wikipedia

2. 下面通過代碼講解,注意了解下注釋；

有關(guān)算法將基于python編寫，如果你是javer，沒有關(guān)系，你可以看的很輕松。

2.1 while循環(huán)方式

# python while循環(huán)版
def binary_search(list, item):
    low = 0
    hight = len(list) - 1
    while low <= hight:
        mid = (low + hight)//2  # 雙斜線表示取整
        guess = list[mid]       # guess表示我們猜測mid位置即為我們要查找的元素
        if(guess == item):      # 如果我們猜中，返回下表
            return mid
        if(guess < item):       # 如果猜測的值比較小 那么我們從新的將區(qū)間定位的較大的區(qū)間
            low = mid + 1
        else:
            hight = mid - 1     # 如果猜測的時間比較大，我們把新的區(qū)間定位到較小的區(qū)間

    return None                 # 未能匹配到值

#test
my_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(my_list, 7))

2.2遞歸方式

# python 遞歸版
def binary_search2(low, hight, item, list):
    if(low > hight):
        return -1
    mid = low + (hight - low)//2 # 計算mid值，注意是 hight-low
    guess = list [mid]
    if(guess == item):
        return mid
    if(guess < item):
        return binary_search2(mid+1, hight, item, list) # 
    if(guess > item):
        return binary_search2(low, mid - 1, item, list)

#test
my_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search2(0, len(my_list)-1, 7, my_list))

2.3運行結(jié)果

image.png