二分查找算法是一个即简单与好用的算法。时间复杂度和空间复杂度都很不错。下面是简单的实现
＃coding:utf-8
＃值得注意的是输入的数组必须是有序的!
def binarySearch(num,target):
low = 0
high = len(num) - 1
while high >= low:
mid = (low + high) // 2 #将原数组二分
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)
网友评论