前言：有个文章
声明！本文和ID：4259470联动出品，搭配米饭食用更佳！
众所不周知，常见的搜索方法有广度优先搜索、深度优先搜索（俗称：深搜广搜）、二分搜索、线性搜索。
正片开始前，请准备好米饭，然后再看目录：
1. 常见搜索方法的概念：
（
（1）、搜索的概念
（2）、线性搜索概念
（3）、二分搜索概念
（4）、深度搜索概念
（5）、广度搜索概念
）
2. 深度搜索模板
3. 广度搜索模板
4. 二分搜索模板
5. 线性搜索模板
正片已开始
1. 常见搜索方法的概念
（1）、搜索的概念
* 在 C++ 编程中，搜索指的是从数据集合（如数组、链表、树、图等）中查找满足特定条件的元素或路径的过程。搜索是程序设计中最基础且常用的操作之一，其效率直接影响程序性能，因此选择合适的搜索算法至关重要!
* 找到目标元素在数据集合中的位置。
* 判断目标元素是否存在于数据集合中。
* 在复杂结构（如树、图）中寻找满足条件的路径或解（如最短路径、可行解）。
（2）、线性搜索概念
* 线性搜索，是一种最简单直观的搜索算法，其核心思想是逐个检查数据集合中的元素，直到找到目标元素或遍历完所有元素。
基本原理：
线性搜索不要求数据集合具备特定的排列顺序，适用于任何类型的线性数据结构（如数组、链表等）。其过程如下：
1. 从数据集合的第一个元素开始
2. 依次将每个元素与目标值进行比较
3. 如果找到匹配的元素，返回其位置（索引）
4. 如果遍历完所有元素仍未找到匹配项，返回表示 "未找到" 的标识（通常为 - 1）
（3）、二分搜索概念
* 二分搜索，是一种高效的查找算法，其核心思想是利用数据的有序性，通过反复将搜索范围减半来快速定位目标元素。
基本原理：
二分搜索仅适用于已排序的数据集合（升序或降序），其过程如下：
1. 确定搜索范围的起始和结束位置
2. 计算中间位置，并比较中间元素与目标值
3. 如果中间元素等于目标值，找到目标，返回其位置
4. 如果中间元素小于目标值，说明目标在右半部分，调整左边界
5. 如果中间元素大于目标值，说明目标在左半部分，调整右边界
6. 重复步骤 2-5，直到找到目标或搜索范围为空（未找到）
（4）、深度搜索概念
* 深度搜索（DFS），又称深度优先搜索，是一种用于遍历或搜索树、图等数据结构的算法。其核心思想是尽可能深地探索一条路径，当无法继续前进时，回溯到上一个节点，选择另一条未探索的路径继续深入，直至遍历所有可达节点。
基本原理：
深度搜索的执行过程类似于 “走迷宫”：优先沿着一条路径走到尽头，遇到死胡同再退回上一个岔路口，选择新的路径继续探索。其过程如下：
1. 从起始节点开始，标记该节点为 “已访问”。
2. 选择一个未访问的相邻节点，递归或通过栈深入探索该节点。
3. 重复步骤 2，直到当前路径无法继续（所有相邻节点均已访问）。
4. 回溯到上一个节点，继续探索其他未访问的相邻节点。
5. 直至所有可达节点均被访问。
（5）、广度搜索概念
* 广度搜索（BFS），又称广度优先搜索，是一种用于遍历或搜索树、图等数据结构的经典算法。其核心思想是从起始节点出发，优先访问距离起始节点最近的所有节点，然后逐层访问更远的节点，类似于水波从中心向四周扩散的过程。
基本原理：
广度搜索的执行过程如同 “逐层扩散”：先访问起始节点的所有直接邻居（距离为 1 的节点），再依次访问这些邻居的所有未访问邻居（距离为 2 的节点），以此类推，直到遍历所有可达节点。其过程如下：
1. 从起始节点开始，将其加入队列并标记为 “已访问”。
2. 当队列不为空时，取出队首节点并访问它。
3. 将该节点所有未访问的相邻节点加入队列，并标记为 “已访问”。
4. 重复步骤 2-3，直到队列为空（所有可达节点均被访问）。
2. 深度搜索模板
时间复杂度：
* 对于包含 n 个节点和 e 条边的图：
邻接表存储时，时间复杂度为 O(n+e)O(n + e)O(n+e)
邻接矩阵存储时，时间复杂度为 O(n2)O(n^2)O(n2)
* 对于树（特殊的图，边数为 n-1）：时间复杂度为 O(n)O(n)O(n)
优缺点：
* 优点：
内存占用通常小于广度优先搜索，尤其对于深度较大但分支较少的结构。
适合解决路径查找、连通性检测、迷宫求解等问题。
* 缺点：
不保证找到最短路径（在无权图中）。
对于深度极大的结构（如深度为 10610⁶106 的树），递归实现可能导致栈溢出。
可能陷入 “深层无效路径”，在某些场景下效率较低。
C++ 实现示例：
终于要写完了吗！？不你错了，当然写不完呀！
3. 广度搜索概念
时间复杂度：
* 对于包含 n 个节点和 e 条边的图：
邻接表存储时，时间复杂度为 O(n+e)O(n + e)O(n+e)
邻接矩阵存储时，时间复杂度为 O(n2)O(n²)O(n2)
* 对于树（特殊的图，边数为 n-1）：复杂度为 O(n)O(n)O(n)
优缺点：
* 优点：
在无权图中，能找到从起始节点到其他节点的最短路径（边数最少）。
适合解决 “层次化” 问题（如按层级遍历树）。
* 缺点：
空间复杂度较高，尤其对于分支较多的结构（队列可能存储大量节点）。
不适合用于检测环路（相比深度搜索更复杂）。
C++ 实现示例:
4. 二分搜索模板
时间复杂度
* 最佳情况：目标元素是中间元素，时间复杂度为 O(1)O(1)O(1)
* 最坏情况和平均情况：时间复杂度均为 O(logn)O(log n)O(logn)（n为元素总数）
* 每次搜索范围减半，经过 log2n\log₂nlog2 n 次比较后即可完成
优缺点
* 优点：效率高，尤其对于大规模数据，性能远优于线性搜索
* 缺点：要求数据必须有序，且仅适用于可随机访问的结构（如数组），不适用于链表
C++实现示例片段（迭代版）
5. 线性搜索模板
时间复杂度
* 最佳情况：目标元素是第一个元素，时间复杂度为 O(1)O(1)O(1)
* 最坏情况：目标元素是最后一个元素或不存在，时间复杂度为 O(n)O(n)O(n)（n为元素总数）
* 平均情况：时间复杂度为 O(n)O(n)O(n)
优缺点
* 优点：实现简单，不要求数据有序，适用于任何线性数据结构
* 缺点：效率较低，尤其当数据量很大时性能表现不佳
C++实现示例
求赞！！！！
真的制作不易！
彩蛋
