二分查找法
算法復(fù)雜度：log2n
簡(jiǎn)單查找復(fù)雜度：n
輸入铭污，輸出
輸入的是一個(gè)有序列表葛作，一個(gè)查找的值，輸出一個(gè)值的位置济似，可能為空矫废。
設(shè)計(jì)與實(shí)現(xiàn)
數(shù)據(jù)結(jié)構(gòu)： 數(shù)組
查找元素的范圍： array[0] <= 查找的元素 <= array[arrray.length-1]
設(shè)計(jì)
二分查找1.jpg
查找范圍在low和high之間
low = 0
high = array.length - 1
二分查找2.jpg
查找的值和mid比較，mid是中間值砰蠢，因?yàn)閿?shù)組中元素已經(jīng)排過(guò)序了,mid應(yīng)該是個(gè)整數(shù)蓖扑，除不盡向下取整
實(shí)現(xiàn)
def binary_search(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (low + high) / 2
guess = list[mid]
if guess == item: //找到了元素，返回下標(biāo)
return mid
if guess > item: //猜的元素在左邊
high = mid - 1
else:
low = mid + 1 //猜的元素在右邊
return None;
print binary_search([1,2,3,4,6,8], 4)
關(guān)鍵點(diǎn)
- 輸入數(shù)據(jù)是有序列表
- 選中間值進(jìn)行比較
- 算法復(fù)雜度log2n
