《算法图解》学习笔记一：二分查找

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法图解》学习笔记一：二分查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1568字，纯文字阅读大概需要3分钟。

内容图文

   假设要在电话簿中找一个名字以K打头的人，现在谁还用电话簿！）可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做，而是从中间开始，因为你知道以K打头的名字在电话簿中间。
   又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。
   现在假设你登录Facebook。当你这样做时，Facebook必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon，Facebook可从以A打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。
   这是一个查找问题，在前述所有情况下，都可使用同一种算法来解决问题，这种算法就是二分查找。
   二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要 查找的元素包含在列表中，二分查找返回其位置；否则返回null。

随便猜想一个1-100的数字来分析二分查找与简单查找的区别：

	简单查找	二分查找
方法	一个数字，一个数字的猜。若猜的数字过大，则再将数字猜小点；若猜的数字过大，则将数字猜大点，直至猜中目标数字	从100的一半50开始猜（无论大小都可排除一半的数字），接下来重复以上步骤，每次猜测的数字都是剩余数字的中间数，直至猜中目标数字
执行的最糟糕的次数	n次	log2n次

二分查找的Python代码：
函数binary_search接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组。

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
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None


my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))  # => 1
print(binary_search(my_list, -1))

• 点赞
• 收藏
• 分享
• • 文章举报

一个摩羯座的程序猿 发布了1 篇原创文章 · 获赞 0 · 访问量 23 私信 关注

内容总结

以上是互联网集市为您收集整理的《算法图解》学习笔记一：二分查找全部内容，希望文章能够帮你解决《算法图解》学习笔记一：二分查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---