二分查找的python实现
# -*— coding:utf8 -*-
# 二分查找
def divided_search(sorted_list, key):
length = len(sorted_list)
if not length:
return False
high = length-1
low = 0
while low <= high:
mid = (high + low) / 2
print "high: %d" % high
print "low: %d" % low
print "mid: %d" % mid
print "===================================="
if key < sorted_list[mid]:
high = mid-1
elif key > sorted_list[mid]:
low = mid + 1
elif key == sorted_list[mid]:
print "find key: %d at %d" % (sorted_list[mid], mid)
return mid
测试执行输出
l = [1, 3, 4, 5, 7, 8, 10, 13, 17, 33, 38, 40, 51, 53, 66]
divided_search(l, 5)
输出：
high: 14
low: 0
mid: 7
====================================
high: 6
low: 0
mid: 3
====================================
find key: 5 at 3
时间复杂度 O()=O(log2n)
总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。 由于n/2k 取整后>=1，即令n/2k=1,可得k=log2n(是以2为底，n的对数)
