读《算法图解》——二分法

读《算法图解》----二分法

To use an analogy, if algorithms were about automobiles, it would be for the person who wants to know how cars work, how they are built, and how one might design fuel-efficient, safe, reliable vehicles for the 21st century. The people who hate algorithms are the ones who just want to know how to drive their car on the highway, just like everyone else.———Peter Norvig

用二分查找最多需要log2n步,而简单查找最多需要n步。

二分法是一种算法,输入是一个有序的元素列表。(敲重点:有序)如果要查找的元素包含在列表中,二分查找返回其位置;否则返回null

通俗点来说是一个聪明的猜数字游戏,100个数字中有一个是期望值。那么不妨从50开始猜,排除一半的数字。如果小了,那么猜75,再排除余下一半的数字。2的7次方为128,所以无论哪个数字都能在7次以内确定下来。

下面是Python的实现:

from math import floor
def binary_search(goal_value, li):
    low = 0
    high = len(li) - 1
    while low <= high:        # 边界条件的确定
        middle = floor((low + high) / 2)  # 地板除,向下圆整
        middle_value = li[middle]
        if middle_value == goal_value:
            return f'element:{middle_value},index:{middle}'
        elif middle_value > goal_value:
            high = middle - 1
        elif middle_value < goal_value:
            low = middle + 1
    return None
if __name__ == '__main__':
      li = [1, 3, 5, 7, 9, 10]
      print(binary_search(5, li))
-----------------------------------------
element:5,index:2
Last modification:May 1st, 2019 at 05:31 pm

Leave a Comment