【算法图解】 之 [二分查找法] 详解
入门算法学习,看的第一本是深入浅出的《算法图解》一书,本博客是对《算法图解》一书的学习笔记,将书中的分享的算法示例用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时间)。