专栏首页CSDN技术头条算法入门,其实可以像读小说一样有趣

算法入门,其实可以像读小说一样有趣

来源 | 《算法图解:像小说一样有趣的算法入门书》

Aditya Bhargava是一位编程爱好者,他至今犹记得购买第一本算法书后的情景:

“我琢磨着目录,心想终于要把这些主题搞明白了。但那本书深奥难懂,看了几周后我就放弃了。直到遇到一位优秀的算法教授后,我才认识到这些概念是多么地简单而优雅”。

  • 业余程序员
  • 编程培训班学员
  • 需要重温算法的计算机专业毕业生
  • 对编程感兴趣的物理或数学等专业毕业生

如果你是上述中任何一种类型的同学,请继续往下看:

算法是一组完成任务的指令。任何代码片段都可视为算法,但这里我们只介绍比较有趣的部分,比如,二分查找。

假设要在电话簿中找一个名字以 K 打头的人,(现在谁还用电话簿!)可以从头开始翻页,直到进入以 K 打头的部分。但你很可能不这样做,而是从中间开始,因为你知道以 K 打头的名字在电话簿中间。

又假设要在字典中找一个以O打头的单词,你也将从中间附近开始。

现在假设你登录 Facebook。当你这样做时,Facebook 必须核实你是否有其网站的账户,因此必须在其数据库中查找你的用户名。如果你的用户名为 karlmageddon,Facebook 可从以 A 打头的部分开始查找,但更合乎逻辑的做法是从中间开始查找。

这是一个查找问题,在前述所有情况下,都可使用同一种算法来解决问题,这种算法就是二分查找。

二分查找是一种算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回null。

下图是一个例子。

下面的示例说明了二分查找的工作原理。我随便想一个1~100的数字。

你的目标是以最少的次数猜到这个数字。你每次猜测后,我会说小了、大了或对了。

假设你从1开始依次往上猜,猜测过程会是这样。

这是简单查找,更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99,你得猜99次才能猜到!

01

更佳的查找方式

下面是一种更佳的猜法。从50开始。

小了,但排除了一半的数字!至此,你知道1~50都小了。接下来,你猜75。

大了,那余下的数字又排除了一半!使用二分查找时,你猜测的是中间的数字,从而每次都将余下的数字排除一半。接下来,你猜63(50和75中间的数字)。

这就是二分查找,你学习了第一种算法!每次猜测排除的数字个数如下。

不管我心里想的是哪个数字,你在7次之内都能猜到,因为每次猜测都将排除很多数字!

假设你要在字典中查找一个单词,而该字典包含240 000个单词,你认为每种查找最多需要多少步?

如果要查找的单词位于字典末尾,使用简单查找将需要240 000步。使用二分查找时,每次排除一半单词,直到最后只剩下一个单词。

因此,使用二分查找只需18步——少多了!一般而言,对于包含 n 个元素的列表,用二分查找最多需要 log2n 步,而简单查找最多需要 n 步。

对数

你可能不记得什么是对数了,但很可能记得什么是幂。log10100相当于问“将多少个10相乘的结果为100”。答案是两个:10 × 10 = 100。因此,log10100 = 2。对数运算是幂运算的逆运算。

对数是幂运算的逆运算

本文使用大O表示法(稍后介绍)讨论运行时间时,log 指的都是 log2。使用简单查找法查找元素时,在最糟情况下需要查看每个元素。因此,如果列表包含8个数字,你最多需要检查8个数字。而使用二分查找时,最多需要检查 log n个元素。如果列表包含8个元素,你最多需要检查3个元素,因为log 8 = 3(23 = 8)。如果列表包含1024个元素,你最多需要检查10个元素,因为 log 1024 = 10(210 =1024)。

下面来看看如何编写执行二分查找的 Python 代码。这里的代码示例使用了数组。如果你不熟悉数组,也不用担心,下一章就会介绍。你只需知道,可将一系列元素存储在一系列相邻的桶(bucket),即数组中。这些桶从0开始编号:第一个桶的位置为#0,第二个桶为#1,第三个桶为#2,以此类推。

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

low = 0high = len(list) - 1

你每次都检查中间的元素。

mid = (low + high) / 2  ←---如果(low + high)不是偶数,Python自动将mid向下取整。guess = list[mid]

如果猜的数字小了,就相应地修改low

if guess < item:
  low = mid + 1

如果猜的数字大了,就修改high。完整的代码如下。

def binary_search(list, item):
  low = 0    (以下2行)low和high用于跟踪要在其中查找的列表部分
  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  ←--------------------别忘了索引从0开始,第二个位置的索引为1print binary_search(my_list, -1) # => None  ←--------------------在Python中,None表示空,它意味着没有找到指定的元素

02

练习

① 假设有一个包含128个名字的有序列表,你要使用二分查找在其中查找一个名字,请 问最多需要几步才能找到?

② 上面列表的长度翻倍后,最多需要几步?

本文分享自微信公众号 - CSDN技术头条(CSDN_Tech)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • eBay开源新数据库技术Kylin,支持TB到PB级数据量

    【编者按】eBay开源了一种名为 Kylin 的数据库技术,eBay在周三的一篇博客上分享了Kylin 的诸多细节,基于 Hadoop 提供 SQL 接口和 O...

    CSDN技术头条
  • Spark Block存储管理分析

    Apache Spark中,对Block的查询、存储管理,是通过唯一的Block ID来进行区分的。所以,了解Block ID的生成规则,能够帮助我们了解Blo...

    CSDN技术头条
  • Apache Kylin 深入Cube和查询优化

    近几年,Apache Kylin作为一个高速的开源分布式大数据查询引擎正在迅速崛起。它充分发挥Hadoop、Spark、HBase等技术的优势,通过对超大规模数...

    CSDN技术头条
  • C/C++语言的查找算法(上)

    算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规...

    C语言与CPP编程
  • 9.2 静态查找表

    1、顺序查找(Sequential Search)的查找过程为:从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,...

    小林C语言
  • 数据结构:查找

    平均查找长度(ASL):在查找的过程中,一次查找的长度是指需要比较的关键字次数,而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。

    HLee
  • 我的软考之路(七)——数据结构与算法(5)之查找

    上篇博文我重点介绍了八大内部排序,这篇博文(数据结构与算法的最后一课)重点介绍查找,我们依旧沿用上篇博文的风格,先简单介绍,再以例子重点讲解。

    程序猿小亮
  • 9.2 静态查找表

    1、顺序查找(Sequential Search)的查找过程为:从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,...

    小林C语言
  • 数据结构:图文详解 - 动态查找、静态查找、散列查找

    对于二分查找存在一定的优 & 缺点,所以衍生出2种二分查找的变式方法:插值查找 & 斐波那契查找。具体如下:

    Carson.Ho
  • 算法与数据结构(九) 查找表的顺序查找、折半查找、插值查找以及Fibonacci查找(Swift版)

    今天这篇博客就聊聊几种常见的查找算法,当然本篇博客只是涉及了部分查找算法,接下来的几篇博客中都将会介绍关于查找的相关内容。本篇博客主要介绍查找表的顺序查找、折半...

    lizelu

扫码关注云+社区

领取腾讯云代金券