搜索算法：二分查找与 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 (不存在)
    }
}