二分法是很常見的一種查找算法曹洽，原理很簡(jiǎn)單，但是要?jiǎng)邮謱?shí)現(xiàn)辽剧，還是有很多細(xì)節(jié)問題要考慮到送淆，下面記錄一下實(shí)現(xiàn)的過程
1.普通實(shí)現(xiàn)
def bisection(arr,num):
top = len(arr)-1 # 查找范圍的上邊界
bottom = 0 # 查找范圍的下邊界
while top>=bottom:
mid = (top+bottom)//2 # 取中間的值，做對(duì)比
if arr[mid] > num:
top = mid -1 # 范圍縮小到前半段
elif arr[mid] < num:
bottom = mid + 1 # 范圍縮小到后半段
else:
print('已找到')
return mid
else:
print('沒找到')
return None
a=[1,3,5,7,9,11,15,18,22,35,36,67,77,78,79,100]
bisection(a, 3)
>>
已找到
1
2.遞歸
def bisection2(lst,n):
if len(lst) == 0:
print('沒找到')
return False
mid = len(lst)//2
if lst[mid] == n:
print('已找到')
return True
elif lst[mid]>n: # 檢查前半部分
return bisection2(lst[:mid],n) # 這里mid不需要減1怕轿，因?yàn)榍衅话ㄓ诌吔? else:
return bisection2(lst[mid+1:],n)
在第一個(gè)例子中偷崩，數(shù)組a的長(zhǎng)度為16辟拷，如果要查詢1的位置，是需要二分次數(shù)最多的阐斜，可以看到while循環(huán)了4次才能找到1衫冻，即2**4=16, log16=4 (2為底)，所以二分法的時(shí)間復(fù)雜度為O(logn)
