数据结构 - 搜索算法

Table of content

在上一节中，我们讨论了各种排序技术以及它们可以使用的场景。然而，排序背后的主要思想是将数据以有序的方式排列，从而更容易在已排序的数据中搜索任何元素。

搜索是在大量数据中查找特定记录（可以是单个元素或一小块数据）的过程。数据可以有多种形式：数组、链表、树、堆和图等。随着当今数据量的不断增加，有多种技术可以执行搜索操作。

数据结构中的搜索算法

可以将各种搜索技术应用于数据结构以检索特定数据。只有当搜索操作返回所需的元素或数据时，才认为搜索操作成功；否则，搜索方法不成功。

这些搜索技术分为两类：

顾名思义，顺序搜索操作会顺序遍历每个数据元素以查找所需数据。此类型的搜索不需要数据以排序方式排列。

示例 - 线性搜索

图1：线性搜索操作

与顺序搜索不同，区间搜索操作要求数据以排序方式排列。此方法通常以区间方式搜索数据；可以通过将数据分成多个子部分或跳过索引来搜索元素。

示例 - 二分搜索、跳跃搜索等。

图2：二分搜索操作

通常，并非所有搜索技术都适用于所有类型的数据结构。在某些情况下，顺序搜索更可取，而在其他情况下，区间搜索更可取。这些搜索技术的评估是通过检查每种搜索方法在特定输入上的运行时间来完成的。

这就是渐近符号出现的地方。要了解有关渐近符号的更多信息，请点击此处。

简单来说，程序运行的时间复杂度有三种不同的情况：

我们主要关注最佳情况和最坏情况的时间复杂度，因为平均情况难以计算。并且由于运行时间基于提供给程序的输入量，因此最坏情况时间复杂度最能描述任何算法的性能。

例如，线性搜索的最佳情况时间复杂度为O(1)，其中在第一次迭代中找到所需元素；而最坏情况时间复杂度为O(n)，当程序遍历所有元素但仍然找不到元素时。这被标记为不成功的搜索。因此，线性搜索的实际时间复杂度被视为O(n)，其中n是输入数据结构中存在的元素数量。

许多类型的搜索方法用于在各种数据结构中搜索数据条目。其中一些包括：

我们将在接下来的章节中详细介绍每种搜索方法。

打印页面