二分查找：变体与边界处理

二分查找的本质

二分查找（Binary Search）：在有序或单调的搜索空间中，每次将搜索范围缩小一半，达到 O(log n) 效率。

核心要求：搜索空间必须有单调性（不一定是排序数组，可以是答案空间）。

三种经典模板

模板一：查找精确值

// 找 target，不存在返回 -1
public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;  // 闭区间 [left, right]
    while (left <= right) {                  // left == right 时区间仍有意义
        int mid = left + (right - left) / 2; // 防溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

模板二：查找左边界（第一个 >= target 的位置）

// 返回 target 在数组中第一次出现的位置（或应该插入的位置）
public int lowerBound(int[] nums, int target) {
    int left = 0, right = nums.length;    // 左闭右开 [left, right)
    while (left < right) {                // left == right 时区间为空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;                 // nums[mid] >= target，收缩右边界
    }
    return left;  // left == right，是第一个 >= target 的位置
}

模板三：查找右边界（最后一个 <= target 的位置）

public int upperBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) left = mid + 1;  // nums[mid] <= target，排除左边
        else right = mid;
    }
    return left - 1;  // 最后一个 <= target 的位置
}

边界处理的记忆技巧

闭区间 [left, right]：
  - while (left <= right)
  - left = mid + 1 / right = mid - 1
  
左闭右开 [left, right)：
  - while (left < right)
  - left = mid + 1 / right = mid

不变量：始终维护"答案在 [left, right] 之内"是二分正确性的保证。

二分答案——搜索空间二分化

当问题满足"如果 x 可行，则 x-1 也可行（单调性）"时，可以在答案空间上二分。

// LeetCode 875 爱吃香蕉的珂珂
// 二分答案：速度 k
public int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = Arrays.stream(piles).max().getAsInt();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(piles, mid, h)) right = mid;  // mid 可行，缩小上界
        else left = mid + 1;
    }
    return left;
}

boolean canFinish(int[] piles, int k, int h) {
    int hours = 0;
    for (int p : piles) hours += (p + k - 1) / k;  // 向上取整
    return hours <= h;
}

在旋转排序数组中查找

// LeetCode 33：旋转数组找 target
// 关键：先判断 mid 在哪个有序段
public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return 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;
}

浮点数二分

// 求平方根（精度控制）
public double mySqrt(double x) {
    double left = 0, right = x;
    while (right - left > 1e-7) {
        double mid = (left + right) / 2;
        if (mid * mid > x) right = mid;
        else left = mid;
    }
    return left;
}

常见陷阱总结

二分的适用特征检查表

• 搜索空间是否有序/单调？
• 是否满足"可行/不可行"的分界线是单调的？
• 答案范围是否已知且有限？
• 判断函数（check function）能否在 O(n) 以内完成？

速查：高频二分题