搜索算法用于在数据结构中查找元素，掌握二分查找、DFS、BFS是必备技能。

搜索算法

搜索算法用于在数据结构中查找特定元素或遍历所有元素。掌握二分查找、DFS 和 BFS 是必备技能。

二分查找 (Binary Search)

在有序数组中查找目标值，每次将搜索范围缩小一半。时间复杂度 O(log n)。

1[0]
3[1]
5[2]
7[3]
9[4]
11[5]
13[6]
15[7]
17[8]
19[9]
搜索范围 中点 找到
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1; // 未找到
}

DFS 深度优先搜索

沿着一条路径走到底，然后回溯。使用栈（递归调用栈）实现。

1
2
3
4
5
6
7
当前节点 已访问
访问顺序: []
// 递归实现
function dfs(node) {
  if (!node) return;

  visit(node);           // 访问当前节点
  dfs(node.left);        // 递归左子树
  dfs(node.right);       // 递归右子树
}

// 迭代实现（使用栈）
function dfsIterative(root) {
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    visit(node);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
}

BFS 广度优先搜索

逐层遍历，先访问离根节点近的节点。使用队列实现。

1
2
3
4
5
6
7
当前节点 队列中 已访问
队列: []
访问顺序: []
function bfs(root) {
  const queue = [root];
  const result = [];

  while (queue.length) {
    const node = queue.shift();
    result.push(node.val);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return result;
}

// 层序遍历（按层分组）
function levelOrder(root) {
  const queue = [root];
  const result = [];

  while (queue.length) {
    const level = [];
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }

  return result;
}

DFS vs BFS 对比

特性DFS 深度优先BFS 广度优先
数据结构栈 (Stack) / 递归队列 (Queue)
遍历顺序纵向深入横向展开
空间复杂度O(h) 树高O(w) 最大宽度
适用场景路径问题、回溯最短路径、层级问题
是否找最短路径否是（无权图）
DFS 适用问题
  • 判断路径是否存在
  • 回溯算法（排列组合）
  • 拓扑排序
  • 检测环
  • 连通分量
BFS 适用问题
  • 最短路径（无权图）
  • 层序遍历
  • 找最近的目标
  • 社交网络关系
  • 迷宫最短路