【算法图解】 之 [二分查找法] 详解

入门算法学习,看的第一本是深入浅出的《算法图解》一书,本博客是对《算法图解》一书的学习笔记,将书中的分享的算法示例用Python3语言实现。 如果你也想要阅读这本书,百度云盘链接: 提取码:【be9k】 或者也可以留言你的邮箱,我将PDF共享给你~

二分查找

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

二分查找工作原理

大家一定玩过‘猜数’这个游戏,就是我随便想一个1~100的数字。 你的目标是以最少的次数猜到这个数字。你每次猜测后,我会说小了、大了或对了。 假设你从1开始依次往上猜,猜测过程会是这样。 这是简单查找,更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99, 你得猜99次才能猜到!

最佳的查找方法是: 这就是二分查找,你学习了第一种算法!每次猜测排除的数字个数如下。 所以,不管我心里想的是哪个数字,你在7次之内都能猜到,因为每次 猜测都将排除很多数字!

仅当列表有序的时候,二分查找才管用!!

二分查找–案例

案例:函数binary_search接收一个"有序数组"和"一个元素"。 如果,指定的元素包含在数组中,这个函数将返回其位置。
def binary_search(list, num):                          
    low = 0                         # 最小索引
    high = len(list) - 1            # 最大索引

    while low <= high:
        mid = int((low + high) / 2)  # 向0取整,中间值的索引
        guess = list[mid]            # 猜中间值

        if guess == num:             # 找到了元素
            return (got %d in index of %d) % (num, mid)

        if guess < num:              # 猜小了,增加最小索引
            low = mid + 1
        else:
            high = mid - 1           # 猜大了,缩小最大索引

    return None

my_list = [1,3,5,7,9]
find_num = 3
print(binary_search(my_list,find_num))
find_num1 = 4
print(binary_search(my_list,find_num1))

----------------------------
got 3 in index of 1
None

运行时间

简单查找逐个地检查数字,如果列表包含100个数字,最多需要猜100次。如果列表包含40亿个数字,最 多需要猜40亿次。换言之,最多需要猜测的次数与列表长度相同,这被称为线性时间(linear time)。

二分查找则不同。如果列表包含100个元素,最多要猜7次;如果列表包含40亿个数字,最多 需猜32次。厉害吧?二分查找的运行时间为对数时间(或log时间)。

经验分享 程序员 微信小程序 职场和发展