1. 二分搜索是什么联逻？
二分搜索（英語：binary search），也叫折半搜索（英語：half-interval search）麦备，是一種在有序數(shù)組中查找特定元素的搜索算法。所以是用二分查找的前提是數(shù)組必須是有序的；時間復雜度屿聋，空間復雜度請參照下圖；有的同學可能對時間復雜度和空間復雜的計算有點繞藏鹊，我又在其他文章中介紹润讥；
圖片來自wikipedia
2. 下面通過代碼講解,注意了解下注釋；
有關算法將基于python編寫盘寡，如果你是javer楚殿，沒有關系，你可以看的很輕松竿痰。
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運行結果
image.png
