写在前面
突然发现一本很有趣的算法书,打算把许久没看的算法捡一下,在进行Flask
框架的学习之前,下定决心要好好地写blog,记录自己的总结和反思。本机环境Ubuntu18.04
,所用编辑器为Remarkable,不过在今天早上最后插公式,软件崩溃后没有保存记录,又得重新构思一遍,现在用Atom替换了它。下面向大家推荐一下数据结构和算法的书籍,数据结构推荐封老师的《大话数据结构》使用C语言实现、算法则推荐自己看第二遍的《算法图解》,使用Python实现。下面让我们走进第一篇,二分查找那不为人知的内心世界。
猜数字游戏
小时候老师让我们做过这么一个趣味游戏:猜数字,他给出了一个1到100之间的数字,然后让全班同学猜,游戏规则是这样的:要是同学猜的数字大了,老师会给出提示:猜大了,同理小的老师也会给出提示,要是正确老师会给出猜对了。一节课就在这么一顿乱猜中结束了,大家都是乱猜,偶尔会瞎猫碰到死耗子,然后结束的时候老师告诉我们,你们可以每次猜中间的数字,这样就可以很快的猜出结果了,之后看到类似的问题,就很快能想到这种方法,但百思不得姐(好吧,其实我没思过)。直到了解了算法才知道为什么需要这么猜,下面让我们进行画面重现。
梦回幼儿园
规则就像刚才说的一样,现在开始猜数字,假设待猜数字为57,让我们先用之前的猜法试一下,一个一个猜,从1开始,这样猜的话,最少得猜57次,6要是99的话,得猜99次,现在让我们试一下从中间开始的猜法。从50开始,则猜数过程如下:
50---->小了、75---->大了、63---->大了、57---->猜对了
从以上过程可以看出,从中间查找,要比一个一个按顺序查找快很多,随着数据规模的增大,这种差异会越来越明显。(感兴趣的话可以自己试一下吧!)下面让我们热烈欢迎今天的主角,二分查找算法。
二分查找算法
猜数字的时候,有个隐含的前提,它给出了一个猜的范围,我们也发现这些序列是连续的,其实从中间开始猜数字就蕴含了二分查找的思想,或者说它就是通过二分查找来实现的,每次排除一半错误的答案,来逼近正确答案,跟学过的对数函数一样
分析之前得了解时间复杂度、空间复杂度及大O表示法,这几个概念,在此假设大家都熟悉这几个知识点(我差不多都忘完了),在此先给出一些常见的大O运行时间(由快到慢排布):
- ,也叫对数时间 ,这样的算法包括二分查找。
- ,也叫线性时间 ,这样的算法包括简单查找。
- ,这样的算法包括快速排序——一种速度较快的排序算法。
- ,这样的算法包括选择排序——一种速度较慢的排序算法。
-
,这样的算法包括旅行商问题的解决方案——一种非常慢的算法。
下面给出代码实现:
def binary_search(list, item):
low = 0 # 查找范围下限
high = len(list) - 1 # 查找范围上限
# print(high)
while(low <= high):
mid = (low + high) // 2 # 下标需为整数
guess = list[mid] # 从中间得到所猜的数
# print(guess)
if(guess == item): # 刚好猜准
return(mid) # 跳出并返回下标
elif(guess < item): # 猜的数字小了,则小于中间数的那一半均小于所猜数
low = mid+1
else: # # 猜的数字大了,则大于中间数的那一半均大于所猜数
high = mid - 1
return(None)
# 测试用例
sea_num = int(input("请输入一个0-10的测试数字,查找不到则返回None:"))
list1 = [2, 4, 5, 6, 9, 10]
print(binary_search(list1, sea_num))
运行结果如下:
网友评论