Data Structures Algorithms 简明教程

Data Structures - Searching Algorithms

在前一节中，我们讨论了各种排序技术以及可以使用它们的情况。然而，执行排序的主要思想是以有序的方式排列数据，使在排序数据中搜索任何元素变得更加容易。

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

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

有两种搜索技术可以归入其中。它们是 -

顾名思义，顺序搜索操作顺序遍历数据的每个元素以查找所需数据。对于这种类型的搜索，数据不必以有序方式排列。

Example - 线性搜索

Fig. 1: Linear Search Operation

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

Example - 二分搜索、跳跃搜索等

Fig. 2: Binary Search Operation

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

这就是渐近符号派上用场的地方。如需详细了解渐近符号，请访问 click here.

简单来说，程序可以有三种不同的时间复杂度情况。它们是：

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

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

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

我们将在以下章节中详细探讨每种搜索方法。