二分搜索算法：函数、收益、时间和空间复杂度

介绍

在任何计算系统中，搜索都是需要开发的最关键的功能之一。 搜索技术用于文件检索、索引和许多其他应用程序。 有许多可用的搜索技术。 其中之一是二进制搜索技术。

二分搜索算法的工作原理是在每次迭代时忽略列表的一半。 它继续拆分列表，直到在给定列表中找到它正在寻找的值。 二分搜索算法是对简单线性搜索算法的快速升级。

无需编码经验。 360° 职业支持。 来自 IIIT-B 和 upGrad 的机器学习和人工智能 PG 文凭。

二分搜索算法的工作

首先要注意的是，二进制搜索算法总是在排序列表上工作。 因此，第一个合乎逻辑的步骤是对提供的列表进行排序。 排序后，将列表的中位数与所需值进行检查。

• 如果期望值等于中心索引的值，则索引作为答案返回。

• 如果目标值低于列表的中心索引的交易，则忽略列表的右侧。

• 如果期望值大于中心索引的值，则丢弃左半部分。

• 然后在短列表上重复该过程，直到找到目标值。

示例 #1

让我们用一个例子来看看这个算法。 假设有一个包含以下数字的列表：

1、15、23、7、6、14、8、3、27

让我们将所需的值设为 27。列表中的元素总数为 9。

第一步是对列表进行排序。 排序后，列表将如下所示：

1、3、6、7、8、14、15、23、27

由于列表中的元素数量为 9，因此中心索引为 5。 索引 5 处的值为 8。将所需的值 27 与值 8 进行比较。首先，检查该值是否等于 8。 如果是，则返回索引并退出。

由于 27 大于 8，我们将忽略左侧部分，只遍历列表的右侧。 要遍历的新列表是：

14、15、23、27

注意：在实践中，列表不会被截断。 只是缩小了观察范围。 因此，不应将“新列表”与制作新列表或缩短原始列表相混淆。 虽然它可以用一个新的列表来实现，但有两个问题。 首先，会有内存开销。 每个新列表都会增加空间复杂度。 其次，每次迭代都需要跟踪原始索引。

新的中心索引可以作为第二个或第三个元素，具体取决于实现。 在这里，我们将把第三个元素视为中心。 将值 23 与值 27 进行比较。由于值大于中心值，我们将丢弃左半部分。

要遍历的列表是：

27

由于列表仅包含一个元素，因此它被认为是中心元素。 因此，我们将期望值与 27 进行比较。当它们匹配时，我们返回原始列表中的索引值 27。

示例 #2

在同一个列表中，让我们假设所需的值为 2。

首先，将中心值 8 与 2 进行比较。由于期望值小于中心值，我们将关注点缩小到列表的左侧。

新的遍历将包括：

1、3、6、7

让我们将中心元素作为第二个元素。 将期望值 2 与 3 进行比较。由于值仍然较小，我们再次将焦点缩小到列表的左侧。

新的遍历将包括：

1

由于遍历列表只有一个元素，因此该值直接与剩余元素进行比较。 我们看到这些值不匹配。 因此，我们使用错误消息跳出循环：未找到值。

数据科学高级认证、250 多个招聘合作伙伴、300 多个学习小时、0% EMI

时间和空间复杂度

二分查找算法的时间复杂度为 O(log n)。 当中心索引直接匹配所需值时，最佳情况的时间复杂度将是 O(1)。 最坏的情况可能是列表两端的值或不在列表中的值。

二分查找算法的空间复杂度取决于算法的实现。 有两种实现方式：

1. 迭代法
2. 递归方法

两种方法完全相同，但在实现上有两个不同之处。 首先，递归方法中没有循环。 其次，它不是将新值传递给循环的下一次迭代，而是将它们传递给下一次递归。 在迭代法中，可以通过循环条件来控制迭代次数，而在递归法中，以最大值和最小值作为边界条件。

在迭代方法中，空间复杂度为 O(1)。 而在递归方法中，空间复杂度为 O(log n)。

好处

• 二分搜索算法是一种实现起来相当简单的搜索算法。

• 这是对线性搜索的显着改进，与一些更难实现的搜索算法相比，它的性能几乎相同。

• 二进制搜索算法在每次迭代时将列表分成两半，而不是按顺序梳理列表。 在大型列表中，此方法非常有用。

结帐：决策树分类：您需要知道的一切

结论

二分搜索算法是计算领域中广泛使用的算法。 它是一种胖而准确的搜索算法，可以在大小数据集上都很好地工作。 二分搜索算法是一种简单且可靠的算法来实现。 通过时间和空间分析，使用这种特殊技术的好处是显而易见的。

如果您想了解数据科学，请查看 IIIT-B 和 upGrad 的数据科学 PG 文凭，该文凭专为在职专业人士而设，提供 10 多个案例研究和项目、实用的实践研讨会、与行业专家的指导、1-与行业导师面对面交流，400 多个小时的学习和顶级公司的工作协助。