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

在这篇文章中，我们将了解线性搜索和二分搜索的区别。

线性搜索

  • 它从数组/列表的开头到结尾进行搜索。

  • 数组/列表中的每个元素都与需要搜索的元素进行比较。

  • 它一直搜索到列表的末尾。

  • 如果找到该元素，则返回一条包含索引的消息。

  • 如果未找到该元素，则返回相关消息。

  • 元素不需要以特定/排序的顺序排列。

  • 它可以实现于任何线性数据结构，如数组、链表。

  • 它基于顺序方法。

  • 建议将其用于小型数据集。

  • 当数组/列表的大小很大时，它的效率较低。

  • 查找元素的最坏情况复杂度为 O(n)，其中‘n’是元素的数量。

  • 查找元素的最佳情况复杂度为 O(1)。

  • 它可以用于一维和多维数组。

二分搜索

  • 要执行二分搜索的数组必须已排序。

  • 要搜索的元素的位置是通过首先找到中间元素来确定的。

  • 中间元素是数组/列表第一个索引和最后一个索引的平均值。

  • 它只能用于具有双向遍历的数据结构。

  • 它基于分治法。

  • 它用于大型数据集。

  • 它在大型数据集上效率更高。

  • 最坏情况复杂度为 O(log2n)，其中‘n’是数组的大小。

  • 查找元素的最佳情况复杂度为 O(1)。

  • 它只能在多维数组上实现。

更新于: 2021年3月24日

3K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告