搜索算法深度解析

一句话概括

搜索算法是计算机科学中最基础也最重要的算法类别之一，本文深入剖析二分查找、深度优先搜索（DFS）和广度优先搜索（BFS）三种核心搜索算法的原理、实现与优化，全部采用 JavaScript 实现并附详细复杂度分析。

背景与意义

搜索算法几乎存在于每一行代码的背后。当你在数组里找一个元素、在地图里寻路、在搜索引擎里检索结果，搜索算法都在默默工作。

从数据结构的角度看，搜索是数据的消费端——无论数据如何存储，最终目的都是被高效地搜索到。一个搜索算法的设计直接影响应用的响应速度、资源消耗和用户体验。

在面试中，搜索算法是考察候选人算法思维的标配。二分查找考察对数思维，DFS/BFS 考察图遍历和递归/迭代能力。掌握这三种搜索算法，等于拿到了算法入门的钥匙。

三类搜索的场景差异

算法	适用场景	数据要求
二分查找	有序数组搜索	数据有序
DFS	全排列、路径搜索、拓扑排序	树/图结构
BFS	最短路径、层序遍历	树/图结构

概念与定义

搜索算法：在数据集合中定位满足特定条件的元素的过程。根据搜索空间的不同分为线性搜索（遍历所有元素）和区间搜索（利用数据特性缩小范围）。

二分查找（Binary Search）：在有序数组中通过不断减半搜索区间来定位目标值，将线性时间复杂度 $O(n)$ 降低到对数级别 $O(\log n)$。

深度优先搜索（DFS）：沿着一条路径深入探索，直到到达叶子节点或死胡同，然后回溯到上一个分叉点继续探索。核心数据结构是栈（递归调用栈或显式栈）。

广度优先搜索（BFS）：从起点出发，一层一层向外扩散，先访问所有距离为 1 的节点，再访问距离为 2 的节点，以此类推。核心数据结构是队列。

核心知识点拆解

1. 二分查找：经典实现与边界处理

二分查找看似简单，实则极易在边界处理上栽跟头。左右闭区间 [left, right] 和左闭右开区间 [left, right) 两种写法均需熟练掌握。

/**
 * 二分查找 - 左闭右闭 [left, right]
 * @param {number[]} nums 已排序数组（升序）
 * @param {number} target 目标值
 * @returns {number} 目标值索引，不存在返回 -1
 * 时间复杂度: O(log n) 空间复杂度: O(1)
 */
function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    // 防止 left + right 溢出，等同于 (left + right) >> 1
    const mid = left + ((right - left) >> 1);
    
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      // 目标在右半区
      left = mid + 1;
    } else {
      // 目标在左半区
      right = mid - 1;
    }
  }
  
  return -1;
}

/**
 * 二分查找 - 左闭右开 [left, right)
 * 区别：right 初值为 nums.length，循环条件为 left < right
 */
function binarySearchLeftOpen(nums, target) {
  let left = 0;
  let right = nums.length;
  
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return -1;
}

变体：查找第一个不小于目标值的元素（Lower Bound）

/**
 * 查找第一个大于等于 target 的下标
 * 常用于「插入位置」场景
 */
function lowerBound(nums, target) {
  let left = 0;
  let right = nums.length;
  
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] >= target) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  
  return left; // 可能返回 nums.length（所有元素都小于 target）
}

关键边界总结：

• 左闭右闭：while (left <= right)，收缩时 mid ± 1
• 左闭右开：while (left < right)，收缩时右边界 right = mid
• 所有边界问题归根结底：你的 right 指向的是「有效元素」还是「无效哨兵」

2. 深度优先搜索（DFS）：递归与迭代

DFS 有两种实现方式：递归（利用调用栈）和迭代（显式栈）。递归写法简洁，迭代写法免除了调用栈溢出的风险。

/**
 * DFS - 二叉树前序遍历（递归）
 * 思路：根节点 → 左子树 → 右子树
 * 时间复杂度: O(n) 空间复杂度: O(h)，h 为树高
 */
function dfsRecursive(root) {
  const result = [];
  
  function traverse(node) {
    if (!node) return;
    
    result.push(node.val);      // 前序：访问根
    traverse(node.left);        // 遍历左子树
    traverse(node.right);       // 遍历右子树
  }
  
  traverse(root);
  return result;
}

/**
 * DFS - 二叉树前序遍历（迭代）
 * 使用显式栈模拟递归过程
 */
function dfsIterative(root) {
  if (!root) return [];
  
  const result = [];
  const stack = [root];
  
  while (stack.length > 0) {
    const node = stack.pop();
    result.push(node.val);
    
    // 注意：先压右子再压左子，保证左子先出栈
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  
  return result;
}

3. BFS：层序遍历与最短路径

BFS 的天然优势在于寻找无权图中的最短路径，因为它按距离递增的顺序访问节点。

/**
 * BFS - 二叉树层序遍历
 * 核心：使用队列，每层一次性处理整层节点
 * 时间复杂度: O(n) 空间复杂度: O(w)，w 为最大层宽
 */
function bfsLevelOrder(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];
  
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];
    
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    result.push(currentLevel);
  }
  
  return result;
}

/**
 * BFS - 网格中的最短路径（LeetCode 1091）
 * 在二进制矩阵中找到从左上到右下的最短路径长度
 */
function shortestPathBinaryMatrix(grid) {
  const n = grid.length;
  if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1;
  
  // 8 个方向
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
  const queue = [[0, 0, 1]]; // [row, col, distance]
  grid[0][0] = 1; // 标记已访问
  
  while (queue.length > 0) {
    const [r, c, dist] = queue.shift();
    
    if (r === n - 1 && c === n - 1) return dist;
    
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      
      if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0) {
        grid[nr][nc] = 1; // 入队前标记，防止重复入队
        queue.push([nr, nc, dist + 1]);
      }
    }
  }
  
  return -1;
}

实战案例

案例一：旋转排序数组中的搜索（LeetCode 33）

这是二分查找的高阶变体。数组原本有序，但在某个未知位置发生了旋转。

/**
 * 搜索旋转排序数组
 * 思路：数组被分为左右两个有序段，通过 nums[left] 与 nums[mid] 的比较
 * 可以判断 mid 落在哪个有序段中，再根据 target 的范围缩小搜索区间
 */
function searchRotated(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    
    if (nums[mid] === target) return mid;
    
    // 判断 mid 落在左有序段还是右有序段
    if (nums[left] <= nums[mid]) {
      // 左段有序
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // 右段有序
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return -1;
}

案例二：岛屿数量（LeetCode 200）

经典 DFS 应用，在二维网格中搜索连通分量。

/**
 * 岛屿数量 - DFS解法
 * 遍历岛屿时将相连的陆地全部标记为已访问
 * 时间复杂度: O(m × n) 空间复杂度: O(m × n)
 */
function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;
  
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  
  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
      return;
    }
    
    grid[r][c] = '0'; // 标记为已访问（沉没岛屿）
    
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }
  
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c); // 沉没整座岛屿
      }
    }
  }
  
  return count;
}

底层原理

二分查找的数学基础

二分查找的本质是减治算法（Decrease and Conquer）——每一轮迭代将问题规模减半，而不是分而治之。

其时间复杂度推导如下：

设数组长度 $n$，每次迭代后搜索范围变为原来的一半：

\[T(n) = T\left(\frac{n}{2}\right) + O(1)\]

展开： \(T(n) = T\left(\frac{n}{4}\right) + O(1) + O(1) = \dots = T(1) + k\cdot O(1)\)

当 $\frac{n}{2^k} = 1$ 时，$k = \log_2 n$，因此 $T(n) = O(\log n)$。

复杂度计算公式也可以理解为：从 $n$ 缩小到 $1$，每次缩小一半，需要 $\log_2 n$ 步。

DFS 与 BFS 的空间复杂度差异

DFS 占用栈空间 $O(h)$（$h$ 为树高或递归深度），在最坏情况下（链状树）可能达到 $O(n)$。BFS 占用队列空间 $O(w)$（$w$ 为最大宽度），在满二叉树最后一层宽度可达 $2^{\log n} = n/2$，所以 BFS 最坏也是 $O(n)$。

关键抉择：

• 树较深但宽度小 → DFS 更省空间
• 树较浅但宽度大 → BFS 更省空间
• 需要最短路径 → 必须用 BFS

DFS 的栈模拟原理

递归调用本质上是操作系统帮我们维护了一个调用栈。每次函数调用，系统将局部变量和返回地址压入调用栈。手动使用栈模拟时，我们需要显式地完成入栈出栈操作。

迭代版 DFS 的优势在于：不受系统调用栈大小限制（通常是 1MB~8MB，JavaScript 引擎约 10000 层递归），并且可以更好地控制执行流程。

高频面试题解析

面试题1：在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）

问题：给定一个升序数组 nums 和目标值 target，找出 target 在数组中的开始位置和结束位置。

解法：使用两次二分查找，一次找左边界，一次找右边界。

function searchRange(nums, target) {
  function findLeft() {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
      const mid = left + ((right - left) >> 1);
      if (nums[mid] >= target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
  
  const leftBound = findLeft();
  if (leftBound >= nums.length || nums[leftBound] !== target) {
    return [-1, -1];
  }
  
  // 找右边界：查找 target + 1 的左边界，然后减一
  function findRight() {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
      const mid = left + ((right - left) >> 1);
      if (nums[mid] >= target + 1) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left - 1;
  }
  
  return [leftBound, findRight()];
}

面试题2：二叉树的层序遍历（LeetCode 102）

问题：给出一棵二叉树，按层序遍历返回节点值。

注意：这道题考的就是 BFS 的标准模板，关键在于每层的节点数控制。

面试题3：全排列（LeetCode 46）

问题：给定一个不含重复数字的数组，返回所有可能的全排列。

function permute(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);
  
  function backtrack(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      
      used[i] = true;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
      used[i] = false; // 回溯
    }
  }
  
  backtrack([]);
  return result;
}

这道题完美展示了 DFS + 回溯的核心模式：选择 → 递归 → 撤销选择。

面试题4：单词搜索（LeetCode 79）

问题：在二维字符网格中查找是否存在目标单词。

考察点：DFS 的变体应用 + 回溯 + 剪枝。

核心思路：从每个格子出发做 DFS，路径与单词匹配则继续深入，不匹配则回溯。用「沉没岛屿」技巧（将访问过的格子临时改为 #）避免重复访问。

面试题5：二分查找的变体——搜索插入位置（LeetCode 35）

问题：给定排序数组和目标值，如果找到目标返回索引，否则返回应该插入的位置。

考察点：二分查找的边界处理。本质上就是 lowerBound 的实现，也是 Java 的 Arrays.binarySearch 返回值的补码运算的基础。

总结与扩展

算法	时间复杂度	空间复杂度	核心数据结构	典型应用
二分查找	$O(\log n)$	$O(1)$	数组指针	有序搜索、数学求根
DFS	$O(n)$	$O(h)$	栈（递归/显式）	全排列、拓扑排序、连通性
BFS	$O(n)$	$O(w)$	队列	最短路径、层序遍历

扩展学习方向：

• 二分查找扩展：浮点数二分（精度控制）、三分查找（凸函数极值）、带权二分（决策单调性优化）
• DFS 扩展：IDDFS（迭代加深 DFS）、回溯算法（约束满足问题）、Alpha-Beta 剪枝
• BFS 扩展：双向 BFS（起点终点同时搜索）、0-1 BFS（边权为 0/1 的最短路）、A* 搜索（启发式搜索）
• JavaScript 注意：递归深度限制（V8 约 10000 层），超深递归必须用迭代实现

搜索算法的核心思想是利用数据的结构特性来减少搜索空间。数据的有序性让我们能用二分查找，图的结构让我们能选择深度优先还是广度优先。掌握这些思想远比背模板更重要——因为真实世界的搜索问题，往往需要你创造性地结合多种策略。