二分查找

二分查找必须是有序集

#!/usr/bin/env python3
def binary_search(array, item):
    low = 0
    high = len(array) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = array[mid]
        if guess == item:
            return mid
        elif guess > item:  # 猜大了
            high = mid - 1
        else:  # 猜小了
            low = mid + 1

    return None


l1 = [1, 3, 6, 11, 24, 58]
l2 = [2, 5, 8, 90]

n1 = binary_search(l1, 11)
n2 = binary_search(l2, 2)

print(n1)
print(n2)

二分查找每次可排除掉一半的元素，最坏的情况下要查找 log(n) 次
算法运行时间是 O(log(n)) 对数级的
大 O 表示法表示的是算法运行时间的上限，表示随着输入规模的增加二分查找运行时间的增长率是对数级的, 对数级的算法增长率较慢