线性搜索和二分搜索的区别

在理解线性搜索和二分搜索的区别之前，我们应该先分别了解线性搜索和二分搜索。

什么是线性搜索？

线性搜索也称为顺序搜索，它一次扫描每个元素。假设我们要在一个数组或列表中搜索一个元素，我们只需计算其长度，而不会跳过任何项。

让我们看一个简单的例子。

假设我们有一个包含 10 个元素的数组，如下图所示

上图显示了一个具有 10 个值的字符类型数组。如果我们想搜索 'E'，搜索将从第 0 个元素开始，扫描每个元素，直到找到元素 'E' 为止。我们不能直接从第 0 个元素跳到第 4 个元素，即每个元素都会逐个扫描，直到找到为止。

线性搜索的复杂度

由于线性搜索会逐个扫描每个元素，直到找到目标元素。如果元素的数量增加，需要扫描的元素数量也会增加。我们可以说，搜索元素所需的时间与元素的数量成正比。因此，最坏情况下的复杂度为 O(n)

什么是二分搜索？

二分搜索是一种搜索方法，通过计算中间元素来检查它比要搜索的元素小还是大。使用二分搜索的主要优点是它不需要扫描列表中的每个元素。它不是扫描每个元素，而是将搜索范围缩小到列表的一半。因此，二分搜索搜索元素所需的时间比线性搜索少。

二分搜索的一个前提条件是数组必须是排序的，而线性搜索可用于排序和未排序的数组。二分搜索算法基于分治技术，这意味着它将递归地分割数组。

二分搜索中有三种情况

情况 1：data<a[mid] 则 left = mid+1。

情况 2：data>a[mid] 则 right=mid-1

情况 3：data = a[mid] // 找到元素

在上述情况中，'a' 是数组的名称，mid 是通过递归计算出的元素索引，data 是要搜索的元素，left 表示数组的左侧元素，right 表示数组右侧的元素。

让我们通过一个例子来理解二分搜索的工作原理。

假设我们有一个大小为 10 的数组，索引从 0 到 9，如下所示

我们要从上面的数组中搜索 70 这个元素。

步骤 1：首先，我们计算数组的中间元素。我们使用两个变量，即 left 和 right。初始时，left =0，right=9，如下所示

中间元素的值可以计算为

因此，mid = 4，a[mid] = 50。要搜索的元素是 70，因此 a[mid] 不等于 data。情况 2 满足，即 data>a[mid]。

步骤 2：由于 data>a[mid]，所以 left 的值增加 mid+1，即 left=mid+1。mid 的值为 4，因此 left 的值变为 5。现在，我们得到了一个子数组，如下所示

现在再次，使用上述公式计算 mid 值，mid 的值变为 7。现在，mid 可以表示为

在上面的图中，我们可以看到 a[mid]>data，所以 mid 的值将在下一步中再次计算。

步骤 3：由于 a[mid]>data，right 的值减去 mid-1。mid 的值为 7，因此 right 的值变为 6。数组可以表示为

mid 的值将再次计算。left 和 right 的值分别为 5 和 6。因此，mid 的值为 5。现在，mid 可以表示在数组中，如下所示

在上面的图中，我们可以看到 a[mid]<data。

步骤 4：由于 a[mid]<data，left 的值增加 mid+1。mid 的值为 5，因此 left 的值变为 6。

现在，使用我们已经讨论过的公式再次计算 mid 值。left 和 right 的值分别为 6 和 6，因此 mid 的值变为 6，如下所示

我们可以在上图中看到 a[mid]=data。因此，搜索完成，元素已成功找到。

线性搜索与二分搜索的区别

以下是线性搜索和二分搜索的区别

描述

线性搜索是一种通过顺序搜索列表中的元素直到找到元素为止来查找元素的搜索方法。另一方面，二分搜索是一种搜索方法，它递归地查找列表中的中间元素，直到中间元素与要搜索的元素匹配。

两种搜索的工作原理

线性搜索从第一个元素开始搜索，一次扫描一个元素，而不跳到下一个元素。另一方面，二分搜索通过计算数组的中间元素将数组分成两半。

实施

线性搜索可以应用于任何线性数据结构，例如向量、单向链表、双向链表。相比之下，二分搜索可以应用于具有双向遍历（即前向和后向遍历）的数据结构。

复杂度

线性搜索易于使用，或者我们可以说它复杂度较低，因为线性搜索的元素可以按任何顺序排列，而二分搜索的元素必须按特定顺序排列。

排序的元素

线性搜索的元素可以按任意顺序排列。在线性搜索中，不强制要求元素按排序顺序排列。另一方面，在二分搜索中，元素必须按排序顺序排列。它可以按递增或递减的顺序排列，算法也会相应更改。由于二分搜索使用排序数组，因此有必要将元素插入到正确的位置。相比之下，线性搜索不需要排序数组，因此新元素可以轻松地插入到数组末尾。

方法

线性搜索使用迭代方法查找元素，因此它也称为顺序方法。相比之下，二分搜索计算数组的中间元素，因此它使用分治方法。

数据集

线性搜索不适用于大型数据集。如果我们想搜索数组的最后一个元素，线性搜索将从第一个元素开始搜索，直到最后一个元素，因此搜索元素所需的时间会很长。另一方面，二分搜索适用于大型数据集，因为它花费的时间更少。

速度

如果线性搜索的数据集很大，那么计算成本将很高，速度也会变慢。如果二分搜索的数据集很大，那么与线性搜索相比，计算成本会更低，速度会更快。

维度

线性搜索可用于单维和多维数组，而二分搜索只能用于一维数组。

效率

当考虑大型数据集时，线性搜索效率较低。在大型数据集的情况下，二分搜索比线性搜索更有效。

让我们以表格形式查看区别。