低成本高效率的图形二进制搜索算法

< p >算法是完成任务的一组指令任何代码片段都可以被视为算法。接下来，我们将讨论二进制搜索，并演示该算法如何提高代码的速度。在一个例子中，该算法将执行的步骤数从40亿减少到32个！

从生活中寻找

假设你想在电话簿中找到一个名字以k开头的人。(现在谁还在使用电话簿？)您可以从头开始翻页，直到进入以k开头的部分但是你可能不这么做，而是从中间开始，因为你知道以k开头的名字在电话簿的中间。

还假设，如果你想在字典中找到一个以o开头的单词，你也可以从中间开始。

现在假设你登录到脸谱网当你这样做的时候，脸谱网必须验证你在它的网站上有一个账户，所以它必须在它的数据库中查找你的用户名。如果你的用户名是karlmageddon，Facebook可以从以A开头的部分开始搜索，但是从中间开始搜索更符合逻辑。

这是搜索问题。在上述所有情况下，可以使用相同的算法来解决问题。这个算法是二进制搜索。

玩小游戏

二进制搜索是一种算法，其输入是元素的有序列表(其原因必须在后面解释)如果要搜索的元素包含在列表中，则二进制搜索返回其位置；否则返回null。

下图是一个例子。

以下示例说明了二进制搜索的工作原理我随便想到一个1 ~ 100的数字。

您的目标是用最少的次数猜测这个数字。每次你猜，我都会说小，大或对

假设你从1开始，一个接一个地猜。猜测过程将是这样的

这是一个简单的搜索，更准确的说是愚蠢的查找每个猜测只能排除一个数字。如果我认为数字是99，你必须猜99次才能猜得到！

最佳搜索方法

下面是一个更好的猜测从50岁开始

很小，但不包括一半的数字！在这一点上，你知道，1 ~ 50是小的。接下来，你猜75

是大的，那么剩下的数字被排除了一半！当使用二进制搜索时，您会猜测中间的数字，这样每次都会将剩余的数字减半。接下来，猜63(50到75之间的数字)

这是二进制搜索。你学会了第一个算法！每个猜测排除的数字如下

不管我在想什么数字，你都可以在7倍内猜出来，因为每次猜出来都会排除很多数字！

假设您想在字典中查找一个单词，并且该字典包含240，000个单词。你认为每次搜索最多能走多少步？

如果要搜索的单词在词典的末尾，使用简单搜索将需要240，000步。使用二进制搜索时，一次排除一半单词，直到只剩下一个单词。

因此，使用二进制搜索只需要18步——少得多！通常，对于包含n个元素的列表，二进制搜索最多需要log2n个步骤，而简单搜索最多需要n个步骤

对数

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

的对数是

书使用大的0符号来讨论运行时时，日志指的是log2当使用简单的搜索方法来查找元素时，您需要在最坏的情况下查看每个元素。因此，如果列表包含8个数字，您最多需要检查8个数字。使用二进制搜索时，最多需要检查n个日志元素。如果列表包含8个元素，您最多需要检查3个元素，因为日志8 = 3(23 = 8)如果列表包含1024个元素，您最多需要检查10个元素，因为log 1024 = 10(210 =1024)

描述

二进制搜索仅在列表排序时有效。例如，电话簿中的姓名是按字母顺序排列的，因此您可以使用二进制搜索来查找姓名。如果名字没有按顺序排列，结果会是什么？

Python代码

让我们看看如何编写执行二进制查找的Python代码这里的代码示例使用数组如果你不熟悉数组，也不要担心。您需要知道的是，您可以在一系列相邻的桶或数组中存储一系列元素。这些桶从0开始编号:第一个桶是#0，第二个桶是#1，第三个桶是#2，依此类推

函数binary_search接受有序数组和元素如果指定的元素包含在数组中，则此函数返回其位置您将跟踪要在其中找到的数组部分——从整个数组开始

l = 0

high = len(list) - 1

您每次都要检查中间元素

mid =(低高)/2 ←如果(低高)不均匀，Python会自动向下舍入中间值。

猜测=列表

如果猜测数较大，修改为高完整的代码如下

def binary_search(列表，项目):

low = 0(下面两行)low和high用于跟踪列表部分

高= len(列表)—1

虽然低 < p >中间=(低高)/2 ↓-检查中间元素

猜测=列表

"算法图"

本书完成了一项不可能的任务:让数学变得有趣和易懂！

你是否渴望学习算法，比如阅读你最喜欢的小说？如果是这样，这本书正是你梦寐以求的！

本书有丰富的例子和插图，以易于理解的方式解释算法，旨在帮助程序员在日常项目中更好地发挥算法的能量。这本书的前三章将帮助你打下基础。其余主要介绍了广泛使用的算法，包括:何时采用贪婪算法或动态规划；哈希表的应用；图形算法；k近邻算法等。