搜索算法深度解析

一句话概括

搜索就是”在数据里找目标”。按数据结构不同，打法完全不同：有序数组用二分查找（O(log n)）、树 / 图用 DFS 或 BFS。面试真正卡人的不是”会不会写”，而是二分的边界、DFS 的回溯、BFS 的层控制这些细节。

掌握这三个，等于拿下了”算法思维”的入场券——LeetCode 一大半题都是它们的变体。

核心知识点

1. 二分查找：减治，每次砍掉一半

前提：数组必须有序。每次取中点，判断目标在左半还是右半，区间减半。核心难点是边界——推荐统一用”左闭右闭 [left, right]“写法。

// 左闭右闭：right 是有效下标，循环含等号，收缩时 mid±1
function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1); // 防溢出写法
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// 变体：lower_bound —— 第一个 >= target 的位置（也是"插入位置"）
function lowerBound(nums, target) {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] >= target) right = mid; // 左闭右开写法
    else left = mid + 1;
  }
  return left;
}

边界口诀：闭区间 while(left<=right) 且 mid±1；开区间 while(left<right) 且 right=mid。别混着用。

2. DFS：一条路走到黑，再回溯

沿一条路径深入，到头就回溯。核心数据结构是栈（递归调用栈或显式栈）。回溯 = 选择 → 递归 → 撤销选择。

// 全排列（LeetCode 46）：经典 DFS + 回溯
function permute(nums) {
  const res = [], used = new Array(nums.length).fill(false);
  (function backtrack(path) {
    if (path.length === nums.length) { res.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;        // 撤销选择
    }
  })([]);
  return res;
}

// 迭代 DFS（显式栈）避免递归栈溢出：
function dfsIter(root) {
  if (!root) return [];
  const res = [], stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    if (node.right) stack.push(node.right); // 先右后左，保证左先出
    if (node.left) stack.push(node.left);
  }
  return res;
}

3. BFS：一层一层扩散，天然最短路径

用队列，逐层访问。在无权图里第一次碰到目标时的距离就是最短距离——这是 BFS 独有的本领，DFS 做不到。

// 层序遍历（LeetCode 102）：用 levelSize 控制每层
function levelOrder(root) {
  if (!root) return [];
  const res = [], queue = [root];
  while (queue.length) {
    const len = queue.length; const level = [];
    for (let i = 0; i < len; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  return res;
}

// 网格最短路径：入队前就标记已访问，防止重复入队
function shortestPath(grid) {
  const n = grid.length;
  if (grid[0][0] === 1) return -1;
  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const queue = [[0, 0, 1]];
  grid[0][0] = 1;
  while (queue.length) {
    const [r, c, d] = queue.shift();
    if (r === n - 1 && c === n - 1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0) {
        grid[nr][nc] = 1; queue.push([nr, nc, d + 1]);
      }
    }
  }
  return -1;
}

复杂度对比：二分 O(log n) / O(1)；DFS O(n) / O(h)；BFS O(n) / O(w)。

其实你每天都在用

• Array.indexOf / includes 的”升级版”：有序大数据用二分，从 O(n) 降到 O(log n)
• 搜索框联想：在排好序的词库里二分定位前缀起点
• 路由匹配：递归遍历路由树 = DFS；找”最近的匹配路由”思路同回溯
• JSON 深层查找某个 key：DFS 递归遍历整棵树
• 最短路径 / 地图导航：无权图 BFS，第一次到达即最短
• 表单校验”全通过才能提交”：DFS 回溯枚举所有校验分支

常见误解（FAQ）

❌ 误区一：”二分查找很简单，闭眼写”

边界是重灾区：写 while(left < right) 却用 right = mid - 1，会漏元素或死循环。面试建议只练一套边界约定（推荐左闭右闭），不要现场混搭。另外 mid = (left+right)/2 在大数下可能溢出，用 left + ((right-left)>>1)。

❌ 误区二：”DFS 和 BFS 随便选，结果一样”

求”是否存在”两者都行，但求”最短路径”必须用 BFS——DFS 找到的路径不一定最短。反过来，求树高 / 直径（要子树完整信息）用 DFS 后序更自然。

❌ 误区三：”BFS 用 shift 出队没问题”

数组 shift 是 O(n)，队列一长性能塌。工程上用 head 指针代替 shift（O(1)），或干脆用链表 / 双端队列。面试题里写出 shift 通常会被追问优化。

❌ 误区四：”回溯就是递归，搞复杂了”

回溯的精髓是”撤销选择”——不撤销，used 数组和 path 就乱套，会重复或漏解。全排列、子集、N 皇后全是”选 → 递归 → 撤”这个模板，背下它比背十道题管用。

一句话总结

搜索的本质是”利用数据结构特征砍搜索空间”：有序就二分、要最短就 BFS、要穷举就 DFS + 回溯；把边界和”选-撤”刻进肌肉记忆，你看到的就不再是题，而是同一套套路的不同外衣。