算法图解(二) 二分查找

好的！来了来了~ 主要还是复习一下排序算法，作为算法的基础，我认为算法就可以从十大排序算法复习开始，算法图解，一集一沉淀！

导语：算法之路–二分查找

作者：变优秀的小白，Click 进入主页

爱好：Americano More Ice !

QQ群(new): 811792998

算法上集：

算法图解(一) 数组与链表

前提知识

大家是否还记得对数呢？你很可能不记得什么是对数了，但你大几率记得什么是幂。 对数运算 = 幂运算的逆运算

图解：

二分查找原理

以python作为算法语言编写

# 定义要查找的数组范围，一头一尾 low = 0 high = len(list) - 1 # 每次检查下中间的元素 # mid为中间值，若mid不为偶数向下取整 mid = (low + high) // 2 guess = list[mid]

# 若guess猜的数字小了，修改low low = mid + 1

当然，若guess猜的数字打了，就修改high

二分查找完整代码实现

def binary_search(list, item): # low，high确定查找范围 low = 0 high = len(list) - 1 # 当缩小到只有一个元素 while low <= high: # 检查中间元素 mid = (low + high) // 2 guess = list[mid] # 若guess找到了item即需要找的数 if guess == item: return mid # 猜大了 if guess > item: high = mid - 1 # 猜小了 else: low = mid + 1 return None

既然已经编写好了二分查找的代码，那怎么才能保证它是准确无误的呢？🙃 这个时候就需要测试代码！让我们编写个测试用例(TestCase)吧~

以下为测试代码：

my_list = [1, 3, 6, 7, 10, 11] # 查找个存在的数的位置，数组索引从0开始！ print(binary_search(my_list, 3)) # 查找个不存在的数 print(binary_search(my_list, 0))

运行结果

课后练习

有兴趣可以做做哦~

假设有一个包含128个名字的有序列表，使用二分查找在其中查找一个名字，最多需要几步可以找到呢？上面列表乘于128后，最多需要多少步呢？

下集预告

算法图解(三) 大O表示法 - 明日更!!

结束语：大家如果遇到什么疑问或者建议的地方，可直接留言评论！作者看到会马上一一回复！

如果小白的博客有建议或批评的，下方留言即可！如果觉得小白此文章有所帮助，留下你的点赞👇🏻，Star Click和收藏❤️哦！谢谢谢！