1.二分查找：適用于查找有序元素列表中的指定元素
特點：列表必須有序 對半拆分
問題：游戲 1-100中厢绝，小明設置一個數(shù)字，小紅猜測，數(shù)字=小明設置正確，數(shù)字<小明設置 小明說小了 胸嘁，數(shù)字>小明設置 小明說大了，最多多少次小紅能猜中數(shù)字凉逛？
使用折半法查找
第一步 100/2 =50 猜50
第二步 50/2 猜25
第三步 25/2 猜13
第四步 13/2 猜7
第五步 7/2 猜4
第6步 4/2 猜2
第7步 2/2 猜1
所以最多7步之內(nèi)，肯定能得到答案
對于任意n個元素的有序序列群井，查找的步驟最多是
k即為最大次數(shù)
log是什么状飞？ log是對數(shù)表達式，那對數(shù)是什么书斜？ 對數(shù)運算是冪運算的逆運算
首先冪運算 比如 10*10=100 即
反過來 求x的值即為對數(shù)運算诬辈， 數(shù)學表達式為是
以下為二分查找python版代碼表達式
# 循環(huán)
def brinary_search_(array, find):
low = 0
height = len(array) - 1
while low <= height:
mid = int((height + low) / 2)
if array[mid] == find: # 比較完中間值 后面無需再比較所以 mid的位置根據(jù)情況+1 or -1
return mid
if array[mid] > find:
height = mid - 1
else:
low = mid + 1
return -1
# 遞歸
def brinary_search(array, find, low, height):
mid = int((height + low) / 2)
if find > array[height] or find < array[low]:
return -1
if array[mid] == find:
return mid
if low > height:
return -1
if array[mid] > find:
return brinary_search(array, find, low, mid - 1)
if array[mid] < find:
return brinary_search(array, find, mid + 1, height)
if __name__ == '__main__':
myArray = [1, 3, 5, 7, 8, 10, 12]
index = brinary_search_(myArray, 6)
index_ = brinary_search(myArray, 8, 0, len(myArray) - 1)
print(index)
print(index_)
