搜索算法：二分查找与 BFS/DFS

这一课你将能做到

1. 手写标准二分查找及其变体（查找边界）
2. 用 DFS/BFS 解决矩阵中的连通性问题
3. 在判题中根据题目特征选择合适的搜索策略

为什么要学

搜索是算法的「探路术」。二分查找在有序数据中极速定位，DFS/BFS 在图和树中遍历所有可能。不会搜索，就像在海量数据中大海捞针。

人话：二分查找是「猜数字游戏」——每次猜中间，根据反馈缩小一半范围；DFS 是「走迷宫」——一条路走到黑，走不通就回头；BFS 是「水波纹」——一圈一圈向外扩散。

先建立图像

二分查找:  [1,3,5,7,9,11,13]
           left=0, right=6, mid=3 → 7
           比 7 小？往左；比 7 大？往右

DFS:      A → B → D → 回溯 → B → E → 回溯 → A → C
          (深度优先，栈实现)

BFS:      A → B → C → D → E
          (广度优先，队列实现)

跟着做

步骤 1：标准二分查找

public class Main {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防溢出
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1; // 没找到
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        System.out.println(binarySearch(arr, 7));  // 3
        System.out.println(binarySearch(arr, 4));  // -1
    }
}

前提：数组已排序。O(log n)。

步骤 2：查找第一个等于 target 的位置（下界）

public class Main {
    public static int lowerBound(int[] arr, int target) {
        int left = 0, right = arr.length; // 注意：right 是开区间
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= target) right = mid; // 答案在左半
            else left = mid + 1;
        }
        return left; // 第一个 >= target 的位置
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 3, 4};
        System.out.println(lowerBound(arr, 2)); // 1
        System.out.println(lowerBound(arr, 5)); // 6 (插入位置)
    }
}

步骤 3：查找最后一个等于 target 的位置（上界）

public class Main {
    public static int upperBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > target) right = mid; // 答案在左半
            else left = mid + 1;
        }
        return left - 1; // 最后一个 <= target 的位置
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 3, 4};
        System.out.println(upperBound(arr, 2)); // 3
        System.out.println(upperBound(arr, 0)); // -1 (不存在)
    }
}

步骤 4：DFS——岛屿数量

public class Main {
    static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右
    
    public static int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    
    static void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length 
            || grid[i][j] != '1') return;
        grid[i][j] = '0'; // 标记已访问
        for (int[] d : dirs) {
            dfs(grid, i + d[0], j + d[1]);
        }
    }
    
    public static void main(String[] args) {
        char[][] grid = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        System.out.println(numIslands(grid)); // 3
    }
}

步骤 5：BFS——最短路径

import java.util.*;

public class Main {
    static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    
    public static int shortestPath(int[][] grid, int[] start, int[] end) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        queue.offer(new int[]{start[0], start[1], 0}); // {x, y, dist}
        visited[start[0]][start[1]] = true;
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            if (curr[0] == end[0] && curr[1] == end[1]) return curr[2];
            for (int[] d : dirs) {
                int ni = curr[0] + d[0], nj = curr[1] + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n 
                    && grid[ni][nj] == 0 && !visited[ni][nj]) {
                    visited[ni][nj] = true;
                    queue.offer(new int[]{ni, nj, curr[2] + 1});
                }
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[][] grid = {
            {0,0,0},
            {1,1,0},
            {0,0,0}
        };
        System.out.println(shortestPath(grid, new int[]{0,0}, new int[]{2,2})); // 4
    }
}

讲清楚要点

1. 二分查找前提：必须有序。变种：查找下界、上界、旋转数组。
2. DFS vs BFS：DFS 用栈（递归），适合求所有解、拓扑排序；BFS 用队列，适合求最短路径、层序遍历。
3. 标记已访问：DFS 可以原地修改（如岛屿题把 '1' 变 '0'），BFS 通常需要 visited 数组。
4. 判题技巧：数据范围 n≤20 可以暴搜；n≤1000 可以 O(n²)；n≤10^5 必须 O(n log n) 或 O(n)。

你可能会懵的地方

• 二分查找的边界条件怎么记？ 记住「循环不变量」：区间 [left, right] 内一定有答案。left <= right 对应闭区间，left < right 对应左闭右开。

• DFS 和 BFS 的空间复杂度？ DFS 是 O(h)，h 是最大深度；BFS 是 O(w)，w 是最大宽度。二叉树中 h=log n，w=n/2。

• 什么时候用 DFS，什么时候用 BFS？ 求最短路径用 BFS；求所有可能解、连通性、拓扑排序用 DFS。内存受限时用 DFS。

• 递归 DFS 会栈溢出吗？ 深度超过 10^4 就可能溢出。改迭代（显式栈）或增大 JVM 栈空间 -Xss512m。

• 双向 BFS 是什么？ 从起点和终点同时 BFS，相遇时结束。能把 O(b^d) 降到 O(b^(d/2))，适合起点终点都知道的最短路径。

错法对照

错法	问题	正解
二分用 mid = (left+right)/2	大数溢出	mid = left + (right-left)/2
二分边界 right = arr.length-1 但循环用 left < right	漏掉最后一个元素	统一用 left <= right 配闭区间
DFS 不标记已访问	死循环或重复计算	访问后立即标记，或传入 visited
BFS 不记录距离	无法求最短路径	队列元素带距离字段，或按层遍历
在 BFS 中修改原数组	影响后续判断	用 visited 数组或复制原数组

卡点急救

1. 二分死循环：检查 left 和 right 的更新是否至少移动一位。left = mid 或 right = mid 都可能死循环，应该是 left = mid + 1 或 right = mid - 1（视情况而定）。
2. DFS 重复访问：进入节点时立即标记，不要等四个方向都试完再标记。
3. BFS 内存爆炸：队列中元素太多。考虑双向 BFS，或 A* 启发式搜索。

面试常问

• 二分查找的边界条件怎么处理？ 记住循环不变量。如果区间是 [left, right]，循环条件 left <= right，更新 left = mid + 1 / right = mid - 1。如果区间是 [left, right)，循环条件 left < right，更新 left = mid + 1 / right = mid。

• DFS 和 BFS 的区别？ DFS 用栈（递归），深度优先，空间 O(h)，适合求所有解；BFS 用队列，广度优先，空间 O(w)，适合求最短路径。DFS 代码简洁，BFS 不易栈溢出。

• 如何找旋转排序数组中的最小值？ 二分。比较 arr[mid] 和 arr[right]：如果 arr[mid] > arr[right]，最小值在右半；否则在左半（含 mid）。

自测三问

1. 二分查找的前提条件是什么？
2. BFS 求最短路径时，为什么第一次到达终点就是最短？
3. DFS 递归实现有什么风险？如何避免？

小结一句话

二分查找在有序数据中极速定位，DFS/BFS 在图和树中遍历所有可能；掌握搜索策略，就掌握了解决复杂问题的钥匙。

延伸

• Java 官方文档：Arrays.binarySearch
• 下一课：树结构——二叉搜索树、AVL 树与堆。