【从0到1学算法】二分查找法

02/05 17:09
阅读数 23

说到算法,大家应该都会脑壳疼吧。除了应付一下面试,准备过算法,也接触过不少算法,但是面试完了,基本上就忘光了。但不得不说,算法真的很重要,算法是解决问的方法,你可能会说根本用不上,那只是因为你根本没有算法的思维,又如何说得上使用呢。在这里,我会和大家一起重学算法,阅读《图解算法》入门算法经典书籍,然后根据个人知识进行整理与补充而编写的文章。今天讲的二分查找法,如果你对这个算法很熟请忽略或者复习一下也未尝不可。

二分查找法

先来看看最简单的查找算法,简单查找法,也可以说是美嘉算法(美嘉经常用到的算法)假设我在1~100的数字中查找56使用美嘉算法是这样的

image

需要经过56次才能得到结果!当我们使用二分查找法的时候是这样的从中间50开始猜image

小了,排除了半的数字! 查找范围缩小至51-100,接下来猜75image

大了,又排除了一半数字!查找范围缩小到51-74,接下来猜62。又大了,再猜56image 只猜了4次便找到了正确答案,这就是算法的力量啊! 100个元素里,最多只需要7次便能找到答案image 这就是二分查找法,每次从中间开始猜,每次可排除一半的数量再举个例子,假设要在包含240000个单词的字典中查找一个单词,最多需要找到少步?使用二分查找法是这样的,最多17步image 简单查找法呢,最多240000步一般而言,对于包含n个元素的列表中,用二分查找法最多需要log2n步,而简单查找最多需要n步即二分查找法的时间复杂度为O(logn),简单查找的时间复杂度为O(n),这里的log指的是log2,大O表示法用来表示算法快慢(下集提前预告)

二分查找算法python代码

def binary_search(list, item):
   low = 0
   high = len(list) - 1
   while low <= high:
       # //表示整除
       mid = (low + high) // 2
       guess = list[mid]
       if guess == item:
           return mid
       elif guess > item:
           high = mid - 1
       else:
           low = mid + 1
   return None

ps:二分查找法只能用于有序列表

学会了没?学会可以自己动手,码一码,用什么都语言无所谓。参考:《算法图解》


文章首发于公众号【KEN DO EVERTHING】 本公众号专注于java相关技术,但不限于java、mysql、python、面试技巧、生活感悟等。分享优质博文,技术干货,学习资源等优质内容。 欢迎关注,一起学习,共成长!

原文出处:https://www.cnblogs.com/KEN-DO-EVERTHING/p/12264524.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部