数据结构 - 搜索算法
在上一节中，我们讨论了各种排序技术及其应用场景。然而，排序的核心思想是将数据有序地排列，以便更容易地在排序后的数据中搜索任何元素。
搜索是在海量数据中查找特定记录的过程，该记录可以是单个元素，也可以是一小块数据。数据可以有多种形式：数组、链表、树、堆和图等。随着数据量的不断增长，如今有多种技术可以执行搜索操作。
数据结构中的搜索算法
各种搜索技术可以应用于数据结构来检索特定数据。只有当搜索操作返回所需的元素或数据时，才称其成功；否则，搜索方法不成功。
这些搜索技术分为两类。它们是 −
顺序搜索
区间搜索
顺序搜索
顾名思义，顺序搜索操作会按顺序遍历数据中的每个元素以查找所需数据。对于此类搜索，数据无需排序。
示例 − 线性搜索
图 1：线性搜索操作
区间搜索
与顺序搜索不同，区间搜索操作要求数据已排序。这种方法通常以区间形式搜索数据；可以通过将数据分成多个子部分或跳过索引来搜索元素。
示例 − 二分查找、跳转查找等
图 2：二分查找操作
评估搜索算法
通常，并非所有搜索技术都适用于所有类型的数据结构。在某些情况下，顺序搜索更可取，而在其他情况下，区间搜索更可取。这些搜索技术的评估是通过检查每种搜索方法在特定输入上的运行时间来完成的。
这时，渐近符号就派上用场了。要了解更多关于渐近符号的信息，请点击此处
简单来说，程序运行时的时间复杂度有三种不同的情况。它们是 −
最佳情况
平均情况
最坏情况
我们主要关注最佳情况和最坏情况的时间复杂度，因为平均情况难以计算。由于运行时间取决于程序的输入量，因此最坏情况的时间复杂度最能描述任何算法的性能。
例如，线性搜索的最佳时间复杂度为 O(1)，即在第一次迭代中找到所需元素；而最坏情况的时间复杂度为 O(n)，即程序遍历所有元素后仍未找到任何元素。这被称为搜索失败。因此，线性搜索的实际时间复杂度为 O(n)，其中 n 是输入数据结构中存在的元素数量。
在各种数据结构中搜索数据条目时，可以使用多种类型的搜索方法。其中一些包括 −
我们将在接下来的章节中详细讨论这些搜索方法。
