数学技巧与逻辑应用完美结合的二分查找

2018-09-26  本文已影响0人  lifanxin

引言

二分查找算法最典型的应用莫过于猜数,假如你的朋友要你猜中他心里想的一个数字,这个数字在0-99之间,你每猜一次,他都会告诉你是否猜中亦或是数字偏大或偏小。那么你会怎样猜测呢?

从0猜到99,猜100次
99猜到0呢,还是100次

666

当然最省事的办法就是:先猜50,如果偏大;再猜25,还是偏大;再猜12,还是偏大;再猜6,还是偏大;再猜3,还是偏大;再猜1,还是偏大;那么就只能是0了!这时你可能会说要是一开始猜0早就结束了,不过你就确定你的好友不会想个99吗!

算法分析

从上面我们可以看出,采用二分法猜测,在最坏的情况我们会猜测log_2100次即最多7次,所以算法复杂度为O(log_2^n);而我们盲目猜测时最坏的结果回达到100次,所以算法复杂度为O(n);当然了你也许会说100次我还承受的了,那么我们来看看这个数1125899906842620,如果从0开始,估计你整个青春都浪费了,而采用二分法呢?我们只需要50次,因为这个数等于2^50方。

Python代码

# -*- coding : utf-8 -*-


def binary_search(array, item):
    low = 0   # 数组下标以0开始计算
    high = len(array) - 1  # 计算数组高位位置

while low <= high:  # 只要范围没有缩小到只剩一个元素
    mid = int((low + high) / 2)  # 二分法精髓,从最中间开始查找;int 向下取整
    guess = array[mid]
    if guess == item:
        return mid
    if guess > item:
        high = mid - 1
    else:
        low = mid + 1
return "Not Found"


if __name__ == "__main__":
    test_array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 21]
    print("寻找1的位置:\n", binary_search(test_array, 1))
    print("寻找14的位置:\n", binary_search(test_array, 14))
上一篇 下一篇

猜你喜欢

热点阅读