二进制搜索算法

by Julia Geist

Julia·盖斯特(Julia Geist)

使用安全摄像机镜头解释二进制搜索算法 (Binary Search Algorithms explained using security camera footage)

Binary search, also known as half-interval search or logarithmic search, is a search algorithm that finds the position of a target value within a sorted array.

二进制搜索(也称为半间隔搜索或对数搜索)是一种搜索算法，用于查找排序数组中目标值的位置。

语境 (Context)

I used to live in a building that had a communal kitchen for over 100 students. As you might imagine, there were almost always dishes that weren’t washed in the sink. A group at my school pitched the idea to put up a Nest Cam to catch culprits and call them out on it using the Nest Cam feed.

我曾经住在一栋有公用厨房的大楼里，可容纳100多名学生。 就像您想象的那样，几乎总是有没有在水槽中洗过的盘子。 我学校的一个小组提出了创建一个Nest Cam来捕捉罪犯的想法，并使用Nest Cam feed将其召唤出来。

To illustrate my point, let’s say you found dirty dishes at 12 pm, and you hadn’t been in the kitchen for a day.

为了说明我的观点，假设您在中午12点发现了脏盘子，而您一天都没有在厨房里。

Think about the way that you would search for the person who left the dishes. Would you watch all 24 hours of footage, from the beginning, until you found the culprit?

考虑一下您寻找离开盘子的人的方式。 从头开始，直到发现罪魁祸首，您是否会观看所有24小时的录像？

Probably not. Most likely you’d be hopping around the footage, checking to see if the dishes were in the sink, say, 12 hours ago — at 12 am. If they were, then you’d know that it happened before 12 am. You might flip back to 10 pm after that. If the dishes aren’t there, you’ve now narrowed down the time frame from 10 pm to 12 am — in other words, you’ve ruled out any time before 10 pm. You’d continue this process until you found the culprit.

可能不是。 例如，您很可能会在画面上跳来跳去，例如12个小时前的凌晨12点，检查盘子是否在水池中。 如果是这样，那么您会知道它发生在上午12点之前。 之后，您可能会回到晚上10点。 如果菜都没有 ，你现在已经缩小的时限从10点至12点-换句话说，你已经晚上10点之前排除了任何时候。 您将继续此过程，直到找到罪魁祸首。

What would have taken you up to 24 hours, if you had watched the footage in its entirety, now only takes a few seconds.

如果您完整地观看了整个视频，那么最多需要24小时才能完成，现在只需几秒钟。

Whether you knew it or not, the specific process we just went through is a binary search! A binary search is a very specific way of hopping back and forth in the footage.

无论您是否知道，我们刚刚经历的特定过程都是二进制搜索！ 二进制搜索是在素材中来回跳动的非常特定的方式。

Namely, the footage is split at its midpoint to check for the dishes each time. Notice how the distance to the midpoint gets exponentially smaller with each click.

即，镜头在其中点被分割以每次检查菜肴。 请注意，每次点击到中点的距离如何呈指数减小。

Binary searches are used to find elements quickly and efficiently. The catch, though, is that binary searches only work when the structure you’re looking through is sorted.

二进制搜索用于快速有效地查找元素。 不过，要注意的是， 二进制搜索仅在您浏览的结构被排序时才起作用 。

In the Nest Cam example, what is the footage sorted by? What are we looking for within that sorted arrangement?

在Nest Cam示例中，素材按什么排序？ 我们在这种排序安排中寻找什么？

In this case, the data we are searching is sorted by time. Time allows for a linear measurement. Therefore, it allows us to perform a binary search to find someone who doesn’t wash their dishes within a matter of seconds.

在这种情况下，我们正在搜索的数据将按时间排序。 时间允许进行线性测量。 因此，它使我们可以执行二进制搜索来查找在几秒钟内不洗碗的人。

We also need something that we’re looking for. In this case, it’s the presence of unwashed dishes in the communal sink.

我们还需要寻找的东西。 在这种情况下，公共水槽中存在未洗碗。

二进制搜索算法 (Binary Search Algorithm)

While programming, a binary search can be used in a multitude of contexts. It’s an extremely quick way to find elements within a sorted structure.

在编程时，可以在多种环境中使用二进制搜索。 这是在排序的结构中查找元素的非常快速的方法。

Binary searches can be implemented in an iterative or recursive fashion. An iterative implementation uses a while loop. Meanwhile, a recursive implementation will call itself from within its own body.

二进制搜索可以迭代或递归的方式实现。 迭代实现使用while循环。 同时，递归实现将在其自身内部进行调用。

In code, I’ll be performing a binary search on a relatively simple, sorted set of data to highlight the core implementation of a binary search.

在代码中，我将对相对简单的排序数据集执行二进制搜索，以突出显示二进制搜索的核心实现。

Given an array of sorted numbers, return True if 53 is an element.

给定一个有序数字数组，如果53是一个元素，则返回True 。

[0, 3, 4, 5, 6, 15, 18, 22, 25, 27, 31, 33, 34, 35, 37, 42, 53, 60]

迭代式 (Iterative)

In the iterative approach, a while loop runs until the range of possibilities is zero. This is done by changing the upper and lower bounds of where we are looking and calculating the middle index of that range.

在迭代方法中，运行while循环直到可能性范围为零。 这是通过更改我们所查看位置的上限和下限并计算该范围的中间索引来完成的。

The range exists between the lower and upper bounds, inclusive of the bounds themselves.

范围存在于上下限之间，包括上限本身。

Before the while loop begins, the lower bound is zero and the upper bound is the length of the array. The upper bound changes if the number we’re looking for is in the first half of the range. The lower bound changes if the number we’re looking for is in the second half of the range.

在while循环开始之前，下限为零，上限为数组的长度。 如果我们要查找的数字在范围的前半部分，则上限会更改。 如果我们要查找的数字在范围的下半部，则下界会改变。

If the while loop finishes, meaning there is a range of length zero, return False.

如果while循环结束，这意味着长度范围为零，则返回False 。

def binarySearch(array, number):   lowerBound = 0   upperBound = len(array)

while lowerBound < upperBound:        middleIndex = int(math.floor(lowerBound + (upperBound —    lowerBound) / 2))        if array[middleIndex] == number:             return True        elif array[middleIndex] < number:             lowerBound += 1        elif array[middleIndex] > number:             upperBound = middleIndex   return False

I’d like to elaborate on this equation:

我想详细说明这个等式：

int(math.floor(lowerBound + (upperBound — lowerBound) / 2))

int(math.floor(lowerBound + (upperBound — lowerBound) / 2))

The length of the range is calculated by subtracting the lower bound from the upper bound. However, knowing how long the range is isn’t enough.

的长度 范围是通过从上限减去下限来计算的。 但是，仅知道范围多远是不够的。

At this point, we don’t know which indexes to check in the array. So we are shifting up the array by the lower bound.

在这一点上，我们不知道要检查数组中的索引。 因此，我们将数组上移下限。

We then divide that by two, and round down, to get the middle index of the range. math.floor returns a float, so we also have to cast the result to an int.

然后，我们将其除以2，然后向下舍入以获得该范围的中间索引。 math.floor返回一个float ，因此我们还必须将结果转换为int 。

递归的 (Recursive)

In the recursive approach, the function will call itself from within its body.

在递归方法中，该函数将在其体内调用自身。

The upper bound in this function is the length of the array passed in. Again, the upper bound changes if the number we’re looking for is in the first half of the array. The lower bound changes if the number we’re looking for is in the second half of the array.

此函数的上限是传入的数组的长度。同样，如果我们要查找的数字在数组的前半部分，则上限也会改变。 如果我们要查找的数字在数组的后半部分，则下界会改变。

def binarySearch(array, number):    middleIndexOfArray = int(math.floor(len(array) / 2))    if middleIndexOfArray == 0:        return False

if array[middleIndexOfArray] == number:        return True   elif array[middleIndexOfArray] > number:        return binarySearch(array[:middleIndexOfArray], number)   elif array[middleIndexOfArray] < number:        return binarySearch(array[middleIndexOfArray:], number)

The function then calls itself, passing in an argument of an array half the length of the array that was its argument.

然后，该函数调用自身，传入一个数组实参，该数组实参的长度是该数组实参的一半。

If there are zero elements in the array, return False.

如果数组中的元素为零，则返回False 。

The code is available on my Algorithms and Data Structures repo — star it to stay updated!

该代码在我的算法和数据结构存储库中可用-对其加注星标以保持更新！

下一步 (Next Steps)

I wrote my first binary search to implement a stochastic sampling algorithm. It generates a sentence based on the frequency of words in a corpus of text.

我编写了第一个二进制搜索以实现随机采样算法。 它根据文本语料库中单词的出现频率生成一个句子。

Feel free to try and build a similar project, which has quite a bit of prep before you can implement the binary search. Or think of your own projects and share them in the comments!

随意尝试构建一个类似的项目，该项目在实现二进制搜索之前已经做了很多准备。 或考虑自己的项目并在评论中分享！

This is the second post of my algorithm and data structures series. In each post, I’ll present a problem that can be better solved with an algorithm or data structure to illustrate the algorithm/data structure itself.

这是我的算法和数据结构系列的第二篇文章。 在每篇文章中，我将介绍一个可以通过算法或数据结构更好地解决的问题，以说明算法/数据结构本身。

Star my algorithms repo on Github and follow me on Twitter if you’d like to follow along!

在Github上为我的算法存储库加注星标，如果您想跟随我，在Twitter上关注我！

翻译自: https://www.freecodecamp.org/news/binary-search-algorithm-7170ae244438/

二进制搜索算法