线性搜索与二分搜索：线性搜索和二分搜索之间的区别

介绍

编程语言中的连续内存分配提供了存储多个数据点的灵活实现。 如果我们想要分离数据并将所有相似的数据合并到一个连续的数据结构（如数组、列表等）中，这可以在其高峰期使用。

连续内存分配在现实世界的应用程序中有许多实现，例如计算机中的操作系统、数据库管理系统等。这种数据结构被认为是一种灵活的数据结构，因为向数组添加新数据点只需要一个时间单位，即； O(1)。

但是当我们想要查看特定条目或搜索特定条目时就会出现问题，因为所有现实世界的应用程序都依赖于数据访问命令。 而且这个任务必须足够快，才能满足处理器和内存的速度。

根据我们为搜索元素所做的比较次数，可以划分出各种搜索算法。

如果我们比较数组中的每个数据点来搜索一个元素，那么它被认为是一个顺序搜索。 但是如果我们通过跳过一些比较只比较几个元素，那么它被认为是一个区间搜索。 但是我们需要一个数组按排序顺序（升序或降序）来对其执行区间搜索。

顺序搜索的时间复杂度是线性的 O(n)，二分搜索（区间搜索的一个例子）的时间复杂度是 O(log n)。 此外，还有其他搜索算法，如指数搜索、跳跃搜索等。

但主要使用线性搜索和二分搜索，其中线性搜索用于随机或未排序的数据，而二分搜索用于已排序和有序的数据。 散列是一种特殊的搜索算法，其中访问数据点的时间复杂度为 O(1)。

我们先来了解一下线性搜索和二分搜索的算法，然后比较一下线性搜索和二分搜索的区别。

线性搜索

正如已经讨论过的，线性搜索算法会比较数组中的每个元素，这是执行此操作的代码。

让我们看一下代码。

我们已经声明了一个 linear_search 函数，它需要一个数组，整数键作为参数。 现在我们需要遍历所有元素并比较它是否与我们的搜索键匹配，所以我们编写了一个循环遍历数组的 for 循环，并且在其中有一个 if 循环来检查该位置的数字是否匹配是否使用搜索键。 如果我们找到匹配项，我们将返回该位置。 如果数组中没有这样的元素，那么我们将在函数末尾返回 -1。

请注意，如果我们有多次出现相同的数字，那么我们将返回其第一次出现的位置。

来到 main 方法，我们已经声明并初始化了一个整数数组。 然后我们正在初始化必须搜索的键。 这里我们对数组和键进行硬编码，但您可以将其更改为用户输入。 现在我们已经获得了元素列表和要搜索的键，调用线性搜索方法并记录返回的索引。 稍后我们将检查返回值并打印索引是否存在键，否则打印键未找到。

二进制搜索

二进制搜索比线性搜索更优化，但必须对数组进行排序才能应用二进制搜索。 这是执行此操作的代码。

让我们看一下代码。

我们已经声明了一个 binary_search 方法，它需要一个排序的整数数组和一个整数键作为参数。 我们正在初始化变量低、高、中。 这里低，高是指针，其中低将位于 0 索引处，而高将位于开始处的 n 索引处。 那么二分查找是如何工作的呢？

首先，我们将计算低和高的中间值。 我们可以将 mid 计算为 (low+high)/2，但有时 high 可能是一个很大的数字，将 low 加到 high 可能会导致整数溢出。 因此，将 mid 计算为 low+(high-low)/2 将是一种最佳方式。

我们会将 mid 的元素与搜索键进行比较，如果找到匹配项，我们将返回索引。 否则我们将检查中间元素是大于键还是小于键。 如果 mid 更大，那么我们只需要检查数组的前半部分，因为数组后半部分中的所有元素都大于键，所以我们将更新 high 为 mid-1。

同样，如果 mid 小于 key，那么我们需要在数组的后半部分进行搜索，因此将 low 更新为 mid+1。 请记住，二分搜索基于递减和征服算法，因为我们在每次迭代中忽略了数组的一半。

回到我们的代码，我们已经构建了 main 方法。 初始化一个排序数组和搜索键，调用二分搜索，并打印结果。

现在我们已经了解了线性搜索和二分搜索的算法，让我们比较这两种算法。

线性搜索与二分搜索

在职的

• 线性搜索遍历所有元素并将它们与必须搜索的键进行比较。
• 二进制搜索明智地减少了必须搜索的数组的大小，并且每次都将键与中间元素进行比较。

数据结构

• 线性搜索对于数组、列表、链表等所有数据结构都很灵活。
• 因为我们需要多向遍历，所以不能对所有数据结构执行二分查找。 所以不能使用像单链表这样的数据结构。

先决条件

• 线性搜索可以对所有类型的数据进行，数据可以是随机的或排序的，算法保持不变。 所以不需要做任何前期工作。
• 二进制搜索仅适用于已排序的数组。 因此对数组进行排序是该算法的先决条件。

用例

• 对于较小且随机排序的数据集，通常首选线性搜索。
• 对于较大且已排序的数据集，二进制搜索是首选。

效力

• 在较大数据集的情况下，线性搜索效率较低。
• 在较大数据集的情况下，二分搜索更有效。

时间复杂度

• 在线性搜索中，最佳情况复杂度为 O(1)，其中元素在第一个索引处找到。 最坏情况的复杂度是 O(n)，其中元素在最后一个索引处找到或元素不存在于数组中。
• 在二分查找中，最佳情况复杂度为 O(1)，其中元素位于中间索引处。 最坏情况的复杂度为 O( log 2 n)。

试运行

假设我们有一个大小为 10,000 的数组。

• 在线性搜索中，最佳情况复杂度为 O(1)，最坏情况复杂度为 O(10000)。
• 在二分查找中，最佳情况复杂度为 O(1)，最坏情况复杂度为 O( log 2 10000)=O(13.287)。

结论

我们已经理解了在数组中访问数据的重要性，理解了线性搜索和二分搜索的算法。 浏览了线性搜索和二分搜索的代码。 比较了线性搜索和二分搜索的区别，做了一个大型例子的dry run。

现在您已经了解了线性搜索和二分搜索之间的区别，尝试为大型 sied 数据集运行这两种代码并比较执行时间，开始探索不同的搜索算法，并尝试实现它们！

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

从世界顶级大学在线学习数据科学课程。 获得行政 PG 课程、高级证书课程或硕士课程，以加快您的职业生涯。