关于二分搜索算法你需要知道的一切

八分钟内掌握二分搜索算法

你如何在英语词典中查到一个词？我知道你不会按照这种方法做：从第一页开始，翻阅每一个词，直到找到你要找的那个词——当然，除非你的词是 “土豚”（aardvark）。但如果你要找的词是 “动物园”(zoo)，这种方法会花很长时间。

你会如何在英语词典中查找一个词呢？

一个更快的方法是在中间打开，然后决定是在字典的前半部分还是后半部分继续搜索。

这种方法是对二分搜索算法的一种宽泛描述，这种算法在一个排序的元素列表中寻找一个元素的位置。它被称为二分搜索（来自拉丁语bīnī：”二乘二，对”），因为它在每次迭代时将数组分成两半，以缩小搜索空间。

让我们来定义一下前面那句话中的专业术语。一个 “算法 “是解决一个问题的方法，就像我们在例子中用来查找一个单词的方法。一个 “元素 “就是我们要找的那个词，而 “元素的排序列表 “就是字典。之所以说是 “排序”，是因为字典里的词是按字母顺序排列的。

算法

本节将让你对二分搜索算法有一个更好的直观感受。首先，我们看一下问题陈述，然后了解一下算法本身，最后，通过一个例子来了解一下算法。

问题陈述

在Leetcode，一个练习编码面试问题的平台上，二分搜索问题被陈述如下[3]：

给出一个由n个元素组成的排序（升序）的整数数组nums和一个目标值target，写一个函数来搜索nums中的目标target。如果目标值存在，返回其索引；否则，返回-1。

输入：排序的数组（nums）和目标值（target）。

输出：目标值的索引。

二分搜索算法

二分搜索算法的工作原理如下：

1. 设置搜索空间等于排序后的数组。

3. 取搜索空间的中间元素，与目标值进行比较。

如果目标值等于中间元素，你就找到了目标值。返回中间元素的索引并终止该函数。

如果目标值小于中间元素，将搜索空间减半，抛弃中间元素右边的所有元素，在其左边继续搜索，因为数组是按升序排序的。重复这个步骤直到找到目标。

如果目标值大于中间元素，则将搜索空间减半，丢弃中间元素左边的所有元素，继续在其右边搜索，因为数组是按升序排序的。

重复这个步骤直到找到目标。

3. 如果数组中没有匹配的元素，返回-1

举例说明

让我们通过一个例子来了解二分搜索算法。在下面的图片中，你可以看到一个排序的数组nums = [3, 7, 8, 9, 14, 16, 17, 22, 24]，n = 9个元素。我们想找到目标target=8的位置。

迭代1：

我们通过称为low和high的起始和结束索引来定义搜索空间。我们设置搜索空间的方法是将low指定为数组中第一个元素的索引（0），high指定为数组中最后一个元素的索引（8）。

我们通过使用公式（low + high）/2得到数组中间元素mid的索引。这个操作执行了一个地板函数，以达到所需的中间元素：mid = (low + high) // 2 = (0 + 8) / 2 = 4

中间元素的值是nums[mid] = nums[4] = 14，因此大于target=8。 因此，中间元素右边的所有元素都可以被丢弃。我们将high更新为(mid – 1) = 4 – 1 = 3，使搜索空间减半。

迭代2：

现在，我们重复第2步。

现在数组中间元素的索引是mid = (low + high) // 2 = (0 + 3) / 2 = 1。中间元素的值是nums[mid] = nums[1] = 7，因此小于target=8。 因此，中间元素左边的所有元素都可以丢弃。我们将low更新为（mid + 1）= 1 + 1 = 2，从而将搜索空间减半。

迭代3：

再次，我们重复步骤2。

现在数组中间元素的索引是mid = (low + high) // 2 = (1 + 3) / 2 = 2。

中间元素的值是nums[mid] = nums[2] = 8，因此等于target = 8。 我们返回mid = 2作为目标的位置并终止该函数。

实现

在这一节中，你将看到Python和C++中二分搜索算法的最基本实现。我们还将看看 Python 和 C++ 中内置的二分搜索函数。

Python

def binary_search(self, nums: List[int], target: int) -> int:    # Set search space equal to sorted list    low = 0    high = len(nums) - 1    while low <= high:        # Get the middle element of the search space        mid = (high + low) // 2        # Compare middle element to target        if nums[mid] == target:            return mid        if target < nums[mid]:            high = mid - 1        else:            low = mid + 1    return -1

你可以使用Python中bisect模块的bisect_left()函数，而不是编写你自己的二分搜索函数，[5]。

from bisect import bisect_lefti = bisect_left(target, nums)

C++

C++的实现看起来如下所示：

int binary_search(vector<int>& nums, int target) {    // Set search space equal to sorted list    int low = 0;    int high = nums.size() -1;    while (low <= high){        // Get the middle element of the search space        int mid = (low + high) / 2;        // Compare middle element to target        if (nums[mid] == target){            return mid;        }        if (target < nums[mid]){            high = mid - 1;        }else{            low = mid + 1;        }    }    return -1;}

用C++实现的二分搜索算法

在C++中，标准模板库（STL）提供了函数lower_bound()，可以像下面的例子[2]那样使用它。还有一个函数binary_search()，它返回一个布尔值，即target是否存在于排序后的数组中，但不包括其位置[1]。

#include <algorithm>i = std::lower_bound(nums.begin(), nums.end(), target);

讨论

二分搜索算法的时间和空间复杂度为。

时间复杂度是对数，为O（log n）[6]。如果n是输入数组的长度，二分搜索算法的最坏情况下的时间复杂度是O(log n)，因为它是在每次迭代时将搜索空间减半来执行的。例如，如果我们想在一个长度为8的数组中找到一个元素，在最坏的情况下需要log?（8）=3次迭代。

空间复杂度为O(1)的常数。因为该算法需要中、低、高三个索引的空间，但每次迭代都没有额外的空间。

与线性搜索算法相比，二分搜索算法的主要优势在于其速度。因为线性搜索算法的概念是遍历数组直到找到目标元素–就像从英语词典的第一页开始查找一个特定的单词——线性搜索算法的时间复杂度是O(n)。

例如，如果我们想在前面的例子中找到长度为8的数组中的一个元素，在最坏的情况下将需要n=8次迭代。而使用二分搜索算法则只需要三次迭代。

然而，二分搜索算法的主要缺点是，它需要一个排序的数组，在每次迭代时丢弃一半的搜索空间。尽管在运行二分搜索算法之前可以对数组进行排序，但排序算法会增加整体的时间复杂度。一般来说，排序的时间复杂度为O(n log n)，比线性搜索算法的线性时间复杂度更差。

下面，你可以看到二分搜索算法、线性搜索算法以及作为预处理步骤的额外排序的二分搜索算法的时间复杂度：

大O总结（图片灵感来自[8]）。

结论

开发算法的最佳方法是将问题分解成你已经知道如何解决的算法，如搜索和排序。这就是为什么了解二分搜索算法可以帮助你写出更好的算法——无论你是软件工程师、数据科学家，还是其他开发算法的人。

了解二分搜索算法可以帮助你编写更好的算法–无论你是软件工程师、数据科学家，还是其他任何人。

这篇文章解释了二分搜索算法的工作原理。该算法在一个排序的列表中寻找一个元素。因为搜索空间是排序的，所以该算法在每次迭代后都会丢弃一半的搜索空间。因此，我们将搜索空间减半，直到找到目标元素。你可以看到下面的算法的视觉摘要。

二分搜索算法在排序列表上比线性搜索算法更有效。它有一个对数的时间复杂度和恒定的空间复杂度。

引用

[1] “C++ reference”, “std::binary_search.” cppreference.com. https://en.cppreference.com/w/cpp/algorithm/binary_search (accessed July 2, 2022)

[2] “C++ reference”, “std::lower_bound.” cppreference.com. https://en.cppreference.com/w/cpp/algorithm/lower_bound (accessed July 2, 2022)

[3] Leetcode, “704. Binary Search.” leetcode.com. https://leetcode.com/problems/binary-search/ (accessed July 2, 2022)

[4] Leetcode, “Learning about Binary Search”. leetcode.com. https://leetcode.com/explore/learn/card/binary-search/ (accessed July 2, 2022)

[5] “Python”, “bisect — Array bisection algorithm.” python.org. https://docs.python.org/3/library/string.html#formatspec (accessed July 2, 2022)

[6] S. Selkow, G. T. Heineman, G. Pollice, Algorithms in a Nutshell (2008), O’Reilly Media.

[7] M. Buss, “Divide and Conquer with Binary Search in Swift”, mikebuss.com. https://mikebuss.com/2016/04/21/binary-search/ (accessed July 2, 2022)

[8] “Big-O Cheat Sheet”, “Know Thy Complexities!”, bigocheatsheet.com. https://www.bigocheatsheet.com/ (accessed July 2, 2022)

原文标题：

Everything You Need to Know About the Binary Search Algorithm

原文链接：

https://towardsdatascience.com/everything-you-need-to-know-about-the-binary-search-algorithm-6bc4f9a3127d

译者简介

欧阳锦，一名在埃因霍温理工大学就读的硕士生。喜欢数据科学和人工智能相关方向。欢迎不同观点和想法的交流与碰撞，对未知充满好奇，对热爱充满坚持。

翻译组招募信息

工作内容：需要一颗细致的心，将选取好的外文文章翻译成流畅的中文。如果你是数据科学/统计学/计算机类的留学生，或在海外从事相关工作，或对自己外语水平有信心的朋友欢迎加入翻译小组。

你能得到：定期的翻译培训提高志愿者的翻译水平，提高对于数据科学前沿的认知，海外的朋友可以和国内技术应用发展保持联系，THU数据派产学研的背景为志愿者带来好的发展机遇。

点击文末“阅读原文”加入数据派团队~