二分查找与变体

二分查找的核心思想

二分查找（Binary Search）的本质是每次排除一半的搜索空间，将 O(n) 的线性查找提升至 O(log n)。

前提条件：序列（或搜索空间）必须是有序的，或者具有某种单调性。

目标：在 [1, 3, 5, 7, 9, 11, 13] 中查找 7

初始：left=0, right=6, mid=3, nums[3]=7 → 命中！

若查找 9：
left=0, right=6, mid=3, nums[3]=7 < 9 → 搜索右半：left=4
left=4, right=6, mid=5, nums[5]=11 > 9 → 搜索左半：right=4
left=4, right=4, mid=4, nums[4]=9 → 命中！

标准二分查找模板

二分查找的边界问题是系统开发中最常见的边界陷阱。推荐使用左闭右闭区间模板：

// 在有序数组中查找 target，返回其下标；不存在返回 -1
int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;  // [left, right] 闭区间
    while (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;
}

为什么用 left <= right？
区间 [left, right] 非空的条件是 left <= right。当 left > right 时，区间为空，搜索结束。

为什么 mid = left + (right - left) / 2？
(left + right) / 2 当两者都很大时可能整数溢出，left + (right - left) / 2 等价但安全。

查找边界：最左侧和最右侧位置

当数组中存在重复元素时，标准二分找到的是"某一个"，而不是"第一个"或"最后一个"。

查找最左侧（第一个 ≥ target 的位置）

// 返回第一个等于 target 的下标；不存在返回 -1
int searchLeftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            right = mid - 1;  // 命中时不返回，继续向左收缩
        }
    }
    // left 是第一个 >= target 的位置
    // 验证：left 没越界 && nums[left] 确实等于 target
    if (left >= nums.length || nums[left] != target) return -1;
    return left;
}

直觉：命中不立即返回，而是把右边界收缩到 mid-1，迫使搜索继续向左找更早出现的位置。最终 left 停在第一个等于 target 的位置。

查找最右侧（最后一个 ≤ target 的位置）

int searchRightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;   // 命中时不返回，继续向右收缩
        }
    }
    // right 是最后一个 <= target 的位置
    if (right < 0 || nums[right] != target) return -1;
    return right;
}

统一理解

把三种二分看成"搜索区间的收缩方向"：

变体：在旋转有序数组中查找

[3, 4, 5, 6, 1, 2] ← 将 [1, 2, 3, 4, 5, 6] 旋转后的数组

直观方法：先二分判断 mid 在左半段还是右半段，再根据 target 的范围决定搜索方向。

int searchRotated(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;  // target 在左半段
            } else {
                left = mid + 1;   // target 在右半段
            }
        } else {                        // 右半段有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;   // target 在右半段
            } else {
                right = mid - 1;  // target 在左半段
            }
        }
    }
    return -1;
}

变体：查找峰值

峰值不需要全局有序，只要局部满足单调性即可二分。

// 找峰值（局部最大值）
// 保证 nums[-1] = nums[n] = -∞，必有峰值
int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {  // 注意：left < right（不是 <=）
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;       // mid 可能是峰值，保留
        } else {
            left = mid + 1;    // mid 不是峰值，向上坡方向走
        }
    }
    return left;  // left == right，即峰值位置
}

二分在"答案值域"上的应用

二分不只能用在"数组下标"上，还能在答案的范围上二分——凡是答案具有单调性（越大越好/越差，或越小越好/越差），都可以用"二分答案 + 检验"。

例题：在 D 天内完成包裹运输

weights = [1,2,3,4,5,6,7,8,9,10], D = 5
最低船重为 15（最优分组方案下）

int shipWithinDays(int[] weights, int days) {
    // 答案下界：最重的单个包裹（每天至少能运这一件）
    // 答案上界：所有包裹重量之和（1 天全运完）
    int left = Arrays.stream(weights).max().getAsInt();
    int right = Arrays.stream(weights).sum();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(weights, days, mid)) {
            right = mid;    // 能完成，尝试更小的运力
        } else {
            left = mid + 1; // 不能完成，运力不够
        }
    }
    return left;
}

// 检验：以 capacity 为船重，能否在 days 天内运完
boolean canFinish(int[] weights, int days, int capacity) {
    int daysNeeded = 1, curLoad = 0;
    for (int w : weights) {
        if (curLoad + w > capacity) {
            daysNeeded++;     // 新开一天
            curLoad = 0;
        }
        curLoad += w;
    }
    return daysNeeded <= days;
}

关键思路：

• 船的运力越大，完成的天数越少（单调性）
• 二分运力，对每个运力值，用贪心检验能否在 days 天内完成
• 找最小的满足条件的运力

二分查找的常见模板对比

# 模板一（标准，查找精确值）
while left <= right:
    if match: return mid
    elif too_small: left = mid + 1
    elif too_big: right = mid - 1

# 模板二（查找边界）
while left < right:    ← 注意 <，不是 <=
    if need_right: left = mid + 1
    else: right = mid  ← 不是 mid - 1
return left            ← 返回 left 或 right（相等）

模板二的 while left < right 保证循环结束时 left == right，直接返回而无需区分。

小结

二分查找的精髓不在于"在有序数组中查数"，而在于把可能的答案范围二分，每次排除一半。

凡是满足以下任一条件，都可以考虑二分：

1. 直接在有序数组上查找
2. 旋转/变形有序数组，仍有局部单调性
3. 答案在某个范围内，且满足"越大越好/越差"的单调性（二分答案）

写对二分的三要素：

1. 区间定义（左闭右闭 or 左闭右开）保持一致
2. mid 计算防溢出：left + (right - left) / 2
3. 循环条件和边界更新要与区间定义匹配