二分查找算法是一個即簡單與好用的算法勉躺。時間復(fù)雜度和空間復(fù)雜度都很不錯组贺。下面是簡單的實現(xiàn)
＃coding:utf-8
＃值得注意的是輸入的數(shù)組必須是有序的!
def binarySearch(num,target):
low = 0
high = len(num) - 1
while high >= low:
mid = (low + high) // 2 #將原數(shù)組二分
midValue = num[mid]
if midValue < target: #target比中值大表明要找的在右邊
low = mid + 1
elif midValue > target:
high = mid - 1
else:
return (mid,midValue) #返回查找的值和索引
if __name__ == '__main__':
num = [0, 1, 3, 5, 6, 7, 8, 9]
print binarySearch(num, 6)
