#创作计划# 常见的搜索方法（不会更新）

lexora_

2025-08-07 15:30:12

发布于：浙江

25阅读

0回复

0点赞

声明！本文和ID：4259470联动出品，搭配米饭食用更佳！

众所不周知，常见的搜索方法有广度优先搜索、深度优先搜索（俗称：深搜广搜）、二分搜索、线性搜索。

正片开始前，请准备好米饭，然后再看目录：

常见搜索方法的概念：
（
（1）、搜索的概念
（2）、线性搜索概念
（3）、二分搜索概念
（4）、深度搜索概念
（5）、广度搜索概念
）
深度搜索模板
广度搜索模板
二分搜索模板
线性搜索模板

正片已开始

1. 常见搜索方法的概念

（1）、搜索的概念

在 C++ 编程中，搜索指的是从数据集合（如数组、链表、树、图等）中查找满足特定条件的元素或路径的过程。搜索是程序设计中最基础且常用的操作之一，其效率直接影响程序性能，因此选择合适的搜索算法至关重要!
找到目标元素在数据集合中的位置。
判断目标元素是否存在于数据集合中。
在复杂结构（如树、图）中寻找满足条件的路径或解（如最短路径、可行解）。

（2）、线性搜索概念

线性搜索，是一种最简单直观的搜索算法，其核心思想是逐个检查数据集合中的元素，直到找到目标元素或遍历完所有元素。

基本原理：

线性搜索不要求数据集合具备特定的排列顺序，适用于任何类型的线性数据结构（如数组、链表等）。其过程如下：

从数据集合的第一个元素开始
依次将每个元素与目标值进行比较
如果找到匹配的元素，返回其位置（索引）
如果遍历完所有元素仍未找到匹配项，返回表示 "未找到" 的标识（通常为 - 1）

（3）、二分搜索概念

二分搜索，是一种高效的查找算法，其核心思想是利用数据的有序性，通过反复将搜索范围减半来快速定位目标元素。

基本原理：

二分搜索仅适用于已排序的数据集合（升序或降序），其过程如下：

确定搜索范围的起始和结束位置
计算中间位置，并比较中间元素与目标值
如果中间元素等于目标值，找到目标，返回其位置
如果中间元素小于目标值，说明目标在右半部分，调整左边界
如果中间元素大于目标值，说明目标在左半部分，调整右边界
重复步骤 2-5，直到找到目标或搜索范围为空（未找到）

（4）、深度搜索概念

深度搜索（DFS），又称深度优先搜索，是一种用于遍历或搜索树、图等数据结构的算法。其核心思想是尽可能深地探索一条路径，当无法继续前进时，回溯到上一个节点，选择另一条未探索的路径继续深入，直至遍历所有可达节点。

基本原理：

深度搜索的执行过程类似于 “走迷宫”：优先沿着一条路径走到尽头，遇到死胡同再退回上一个岔路口，选择新的路径继续探索。其过程如下：

从起始节点开始，标记该节点为 “已访问”。
选择一个未访问的相邻节点，递归或通过栈深入探索该节点。
重复步骤 2，直到当前路径无法继续（所有相邻节点均已访问）。
回溯到上一个节点，继续探索其他未访问的相邻节点。
直至所有可达节点均被访问。

（5）、广度搜索概念

广度搜索（BFS），又称广度优先搜索，是一种用于遍历或搜索树、图等数据结构的经典算法。其核心思想是从起始节点出发，优先访问距离起始节点最近的所有节点，然后逐层访问更远的节点，类似于水波从中心向四周扩散的过程。

基本原理：

广度搜索的执行过程如同 “逐层扩散”：先访问起始节点的所有直接邻居（距离为 1 的节点），再依次访问这些邻居的所有未访问邻居（距离为 2 的节点），以此类推，直到遍历所有可达节点。其过程如下：

从起始节点开始，将其加入队列并标记为 “已访问”。
当队列不为空时，取出队首节点并访问它。
将该节点所有未访问的相邻节点加入队列，并标记为 “已访问”。
重复步骤 2-3，直到队列为空（所有可达节点均被访问）。

2. 深度搜索模板

时间复杂度：

对于包含 n 个节点和 e 条边的图：

邻接表存储时，时间复杂度为 $O(n + e)$
邻接矩阵存储时，时间复杂度为 $O(n^2)$
对于树（特殊的图，边数为 n-1）：时间复杂度为 $O(n)$

优缺点：

优点：

内存占用通常小于广度优先搜索，尤其对于深度较大但分支较少的结构。

适合解决路径查找、连通性检测、迷宫求解等问题。
缺点：

不保证找到最短路径（在无权图中）。

对于深度极大的结构（如深度为 $10⁶$ 的树），递归实现可能导致栈溢出。

可能陷入 “深层无效路径”，在某些场景下效率较低。

C++ 实现示例：

#include <vector>
#include <iostream>
using namespace std;

// 递归实现DFS
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    // 标记当前节点为已访问
    visited[node] = true;
    cout << node << " ";  // 访问节点（此处为打印节点值）
    
    // 递归访问所有未访问的相邻节点
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, visited, neighbor);
        }
    }
}

// 初始化并启动DFS
void startDFS(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);  // 记录节点是否被访问
    dfs(graph, visited, start);
}

// 示例用法
int main() {
    // 图的邻接表：节点0-4的连接关系
    vector<vector<int>> graph = {
        {1, 2},    // 节点0连接1和2
        {0, 3, 4}, // 节点1连接0、3、4
        {0},       // 节点2连接0
        {1},       // 节点3连接1
        {1}        // 节点4连接1
    };
    
    startDFS(graph, 0);  // 从节点0开始DFS
    return 0;
}

终于要写完了吗！？不你错了，当然写不完呀！

3. 广度搜索概念

时间复杂度：

对于包含 n 个节点和 e 条边的图：

邻接表存储时，时间复杂度为 $O(n + e)$
邻接矩阵存储时，时间复杂度为 $O(n²)$
对于树（特殊的图，边数为 n-1）：复杂度为 $O(n)$

优缺点：

优点：

在无权图中，能找到从起始节点到其他节点的最短路径（边数最少）。

适合解决 “层次化” 问题（如按层级遍历树）。
缺点：

空间复杂度较高，尤其对于分支较多的结构（队列可能存储大量节点）。

不适合用于检测环路（相比深度搜索更复杂）。

C++ 实现示例:

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

void bfs(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);  // 记录节点是否被访问
    queue<int> q;
    
    // 初始化：起始节点入队并标记
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        // 取出队首节点并访问
        int node = q.front();
        q.pop();
        cout << node << " ";  // 访问节点（此处为打印节点值）
        
        // 将所有未访问的相邻节点入队
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

// 示例用法
int main() {
    // 图的邻接表：节点0-4的连接关系
    vector<vector<int>> graph = {
        {1, 2},    // 节点0连接1和2
        {0, 3, 4}, // 节点1连接0、3、4
        {0},       // 节点2连接0
        {1},       // 节点3连接1
        {1}        // 节点4连接1
    };
    
    bfs(graph, 0);  // 从节点0开始BFS
    return 0;
}

4. 二分搜索模板

时间复杂度

最佳情况：目标元素是中间元素，时间复杂度为 $O(1)$
最坏情况和平均情况：时间复杂度均为 $O(log n)$ $O (l o g n)$ （n为元素总数）
- 每次搜索范围减半，经过 $\log₂n$ 次比较后即可完成

优缺点

优点：效率高，尤其对于大规模数据，性能远优于线性搜索
缺点：要求数据必须有序，且仅适用于可随机访问的结构（如数组），不适用于链表

C++实现示例片段（迭代版）

// 在升序数组中执行二分搜索
int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        // 计算中间索引，避免(left + right)可能导致的溢出
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;  // 找到目标，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1;  // 目标在右半部分
        } else {
            right = mid - 1;  // 目标在左半部分
        }
    }
    
    return -1;  // 未找到目标
}

5. 线性搜索模板

时间复杂度

最佳情况：目标元素是第一个元素，时间复杂度为 $O(1)$
最坏情况：目标元素是最后一个元素或不存在，时间复杂度为 $O(n)$ （n为元素总数）
平均情况：时间复杂度为 $O(n)$

优缺点

优点：实现简单，不要求数据有序，适用于任何线性数据结构
缺点：效率较低，尤其当数据量很大时性能表现不佳

C++实现示例

// 在数组中执行线性搜索
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;  // 找到目标，返回索引
        }
    }
    return -1;  // 未找到目标
}