二分查找

二分查找的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/2^k 取整后>=1，即令n/2^k=1,可得k=log2n(是以2为底，n的对数)