畅销书《算法图解》留言送5本

大家知道“猜数字”这个游戏吗？顾名思义就是一个人想一个数字，另一个人猜。这个游戏简单又有趣，小编小时候很喜欢玩。游戏开始了！小伙伴从 1～100 中任选一个数字记在心里让我猜，我每猜一个数字，他只能说小了、大了或对了。直到我猜到数字，游戏结束。那时的我比较笨，总是从 1 开始依次往上猜……1，小了。那就是 2，2 也小。那就是 3……就这样一个一个猜测数字花费了很长时间。如果他定的数字是 99，那我要猜 99 次才能猜到！小伙伴表示很无奈，后来也不想再和我玩了。
长大之后的一次偶然的机会，我看到了一本书叫《算法图解》。这本书上竟然提到了小时候我玩的“猜数字”游戏，我才了解到，这个游戏不是最终猜到这个数字就算赢，而是又快又准确地猜到数字，那才是高手！那如何快速准确地猜到数字呢？书中告诉了我们“猜数字”游戏快速胜出的小窍门，让我大呼神奇，茅塞顿开。首先从 50 开始猜。小了，但我们可以排除一半的数字！1～50 都小了。接下来，猜 75。大了，那余下的数字又排除了一半！75～100 都可以排除。接下来，猜 63（50 和 75 中间的数字）。大了，但又可以排除一半数字！可以从 51～62 中选了！
接下来，猜 57（50 和 63 中间的数字）。对了！
书中说到，这种猜测方式其实就是算法的二分查找。没想到小小的游戏也用到了算法。使用这种方法每次都能排除一半的数字。不管定数字的人心里想的是哪个数字，在 7 次之内都能猜到。而我小时候一个一个数字排除的那种方法其实也是一种方法，叫简单查找，只不过这种方法比较笨。相比于简单查找，二分查找大大节省了时间提高了效率。那么使用二分查找可节省多少时间呢？简单查找逐个地猜测数字，上面 100 个数字，最多需要猜 100 次。如果从 40 亿个数字中猜呢？最多需要猜 40 亿次。最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）。如果用二分查找的方式，二分查找的运行时间为对数时间（或 log 时间）。100 个数字，最多要猜 7 次；40 亿个数字，最多只需猜 32 次。厉害吧？看看是不是节省了很多时间呢？后来我再玩这个游戏，使用了二分查找方法，总是能很快的猜对，所向披靡，屡战屡胜。其实不光是在这个游戏中二分查找起到很大的作用，在日常的工作生活中，使用二分查找也同样可以大大提高效率，节约时间，帮助我们解决问题。比如，一个工人要维修一条 10km 长的电话线，想迅速查出故障所在。如果沿着线路一小段一小段查找，就很困难要花费很长时间（简单查找）。如果使用二分查找，把电线两端设为 A、B，中点为 C，发现 BC 段有故障，再找到 BC 中点 D，发现 CD 段有故障，再找到 CD 中点 E……这样每查一次，待查线路长度就缩减了一半，经过 7 次查找，就可以找到故障发生的范围了。二分查找这么厉害，那下面我们再来看看如何编写执行二分查找的 Python 代码吧！这里的代码示例使用了数组。可将一系列元素存储在一系列相邻的桶（bucket），即数组中。这些桶从 0 开始编号：第一个桶的位置为 #0，第二个桶为 #1，第三个桶为 #2，以此类推。
函数 binary_search 接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。我们将跟踪要在其中查找的数组部分——开始时为整个数组。

我们每次都检查中间的元素。

作者：【美】巴尔加瓦（Aditya Bhargava）

本书特色

• 你一定能看懂的算法基础书

• 代码示例基于 Python

• 400 多个示意图，生动介绍算法执行过程

• 展示不同算法在性能方面的优缺点

• 教会你用常见算法解决每天面临的实际编程问题

你问我答

目录

大佬推荐

——Amit Lamba，Tech Overture

算法学习起来一点都不乏味！在我和学生们看来，本书既活泼有趣又富有洞见。

作译者介绍

作者

Aditya Bhargava

软件工程师，兼具计算机科学和美术方面的教育背景，在 adit.io 撰写编程方面的博客。

译者

袁国忠

自由译者；2000 年起专事翻译，主译图书，偶译新闻稿、软文；出版译著 40 余部，其中包括《Python编程：从入门到实践》《C++ Prime Plus中文版》《CCNA学习指南》《CCNP ROUTE学习指南》《面向模式的软件架构：模式系统》《风投的选择：谁是下一个十亿美元级公司》等，总计 700 余万字；专事翻译前，从事过三年化工产品分析和开发，做过两年杂志和图书编辑。

关注视频号，并在文下留言

第1/2/8/21/34楼留言中书一本