搜索算法用于在数据结构（例如数组、链表、树或图）中搜索一个或一组满足特定条件的元素。
搜索算法可根据实现思路分为以下两类。
- 通过遍历数据结构来定位目标元素，例如数组、链表、树和图的遍历等。
- 利用数据组织结构或数据包含的先验信息，实现高效元素查找，例如二分查找、哈希查找和二叉搜索树查找等。
1. 暴力搜索
暴力搜索通过遍历数据结构的每个元素来定位目标元素。
1. 线性搜索
- 适用于数组和链表等线性数据结构。
- 顺序地逐个检查数据结构中的每个元素，直到找到目标元素或搜索完整个数据结构。
- 时间复杂度为**O(n)**，其中n是数据结构中的元素数量。
2. 图搜索
- 用于在图/树中查找特定的节点或路径，即深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）
- 广度优先搜索从初始节点开始逐层搜索，由近及远地访问各个节点。
- 深度优先搜索从初始节点开始，沿着一条路径走到头，再回溯并尝试其他路径，直到遍历完整个数据结构。
- 时间复杂度取决于图的结构和算法的实现方式。
2. 自适应搜索
自适应搜索利用数据的特有属性（例如有序性）来优化搜索过程，从而更高效地定位目标元素。
1. 二分搜索
- 仅适用于已排序的数据结构（如有序数组），通过不断将搜索范围减半来定位目标元素。
- 时间复杂度为**O(log n)**。
2. 哈希查找
- 利用哈希表将搜索数据和目标数据建立为键值对映射，从而实现查询操作。
- 时间复杂度通常为**O(1)**，但在冲突较多的情况下可能会降低到O(n)。
3. 树查找
- 通过有序的树结构和特定的查找算法（如递归或迭代）来查找目标元素。
- 包括二叉搜索树（Binary Search Tree，BST）、平衡二叉树（Balanced Binary Tree，如AVL树、红黑树）、B树等。
- 平均情况下的时间复杂度取决于树的高度，**通常为O(log n)**，但在最坏情况下可能为O(n)。