设计与分析 - 搜索技术

在上一节中，我们讨论了各种排序技术及其使用案例。然而，执行排序背后的主要思想是以有序的方式排列数据，以便更容易地搜索排序数据中的任何元素。

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

数据结构中的搜索技术

可以对数据结构应用各种搜索技术来检索某些数据。仅当搜索操作返回所需的元素或数据时，才称其成功；否则，该搜索方法不成功。

这些搜索技术分为两类。他们是 -

顾名思义，顺序查找操作就是顺序遍历数据的每个元素来查找想要的数据。对于此类搜索，数据不需要采用排序方式。

示例- 线性搜索

图 1：线性搜索操作

与顺序搜索不同，区间搜索操作要求数据是有序的。这种方法通常是按间隔搜索数据；可以通过将数据划分为多个子部分或跳过索引来搜索元素来完成。

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

图 2：二分查找操作

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

这就是渐近符号发挥作用的地方。要了解有关渐近符号的更多信息，请单击此处。

简单地解释一下，程序可以运行三种不同的时间复杂度情况。他们是 -

我们主要关注最好情况和最坏情况的时间复杂度，因为平均情况很难计算。由于运行时间取决于程序的输入量，因此最坏情况的时间复杂度最能描述任何算法的性能。

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

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

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