docs/chapter_searching/searching_algorithm_revisited.md
<u>搜索算法（searching algorithm）</u>用于在数据结构（例如数组、链表、树或图）中搜索一个或一组满足特定条件的元素。
搜索算法可根据实现思路分为以下两类。
不难发现，这些知识点都已在前面的章节中介绍过，因此搜索算法对于我们来说并不陌生。在本节中，我们将从更加系统的视角切入，重新审视搜索算法。
暴力搜索通过遍历数据结构的每个元素来定位目标元素。
暴力搜索的优点是简单且通用性好，无须对数据做预处理和借助额外的数据结构。
然而，此类算法的时间复杂度为 $O(n)$ ，其中 $n$ 为元素数量，因此在数据量较大的情况下性能较差。
自适应搜索利用数据的特有属性（例如有序性）来优化搜索过程，从而更高效地定位目标元素。
此类算法的优点是效率高，时间复杂度可达到 $O(\log n)$ 甚至 $O(1)$ 。
然而，使用这些算法往往需要对数据进行预处理。例如，二分查找需要预先对数组进行排序，哈希查找和树查找都需要借助额外的数据结构，维护这些数据结构也需要额外的时间和空间开销。
!!! tip
自适应搜索算法常被称为查找算法，**主要用于在特定数据结构中快速检索目标元素**。
给定大小为 $n$ 的一组数据，我们可以使用线性搜索、二分查找、树查找、哈希查找等多种方法从中搜索目标元素。各个方法的工作原理如下图所示。
上述几种方法的操作效率与特性如下表所示。
<p align="center"> 表 <id> 查找算法效率对比 </p>| 线性搜索 | 二分查找 | 树查找 | 哈希查找 | |
|---|---|---|---|---|
| 查找元素 | $O(n)$ | $O(\log n)$ | $O(\log n)$ | $O(1)$ |
| 插入元素 | $O(1)$ | $O(n)$ | $O(\log n)$ | $O(1)$ |
| 删除元素 | $O(n)$ | $O(n)$ | $O(\log n)$ | $O(1)$ |
| 额外空间 | $O(1)$ | $O(1)$ | $O(n)$ | $O(n)$ |
| 数据预处理 | / | 排序 $O(n \log n)$ | 建树 $O(n \log n)$ | 建哈希表 $O(n)$ |
| 数据是否有序 | 无序 | 有序 | 有序 | 无序 |
搜索算法的选择还取决规模、搜索性能要求、数据查询与更新频率等。
线性搜索
二分查找
哈希查找
树查找