二分算法：边界查找与答案二分模板

二分的本质不是“在有序数组里找数”，而是在一个存在单调边界的搜索空间中定位分界点。本文用统一的半开区间模板推导精确查找、前驱/后继、重复元素边界与答案二分，并配套 LeetCode 题型。

目录

适用条件与统一模型

二分查找要求的并非一定是“数组有序”，而是搜索空间中存在一个可以判断方向的单调性质。若谓词 ok(x) 满足下面任一种形态，就能二分：

第一个 true 的形态：false false false true true true
最后一个 true 的形态：true  true  true  false false false

先写谓词，再写二分。 “答案满足什么条件”比“left 应该怎么移动”更重要；边界移动只是谓词单调性的直接结果。

选模板的决策图

复杂度与前提

• 每轮排除至少约一半候选，时间复杂度为 O(log n)；只使用常数个变量，空间复杂度为 O(1)。
• 数组二分依赖 O(1) 随机访问；链表取中点是 O(n)，通常没有收益。
• 对答案二分，复杂度是 O(log R × check)：R 是答案值域大小，check 是一次可行性检查的成本。

与 排序与搜索 中“排序 + 搜索”的概览不同，本文将所有变体收敛成边界模板，重点解释不变量与可迁移性。

区间与循环不变量

本文固定使用左闭右开区间 [left, right)：left 可以取 0，right 可以取 n，即使数组为空也天然成立。

对于“找第一个满足 predicate(i) 的位置”，维护：

1. [0, left) 中的元素都不满足谓词；
2. [right, n) 中的元素都满足谓词；
3. 尚未确定的候选只在 [left, right)。

当 left == right，候选区间为空，二者正好相遇在第一个满足谓词的位置；若整个数组都不满足，则返回 n。

// 所有下标均在 [0, n)；right = n 是合法的“尾后位置”。
int left = 0;
int right = n;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (predicate(mid)) {
        right = mid;      // mid 可能正是第一个满足者，不能丢弃
    } else {
        left = mid + 1;   // mid 已确认不满足，安全排除
    }
}
return left;

left < right 配合 [left, right)，left <= right 配合 [left, right]。 两套写法都正确，但不能混用初始化、循环条件与更新规则。

核心模板

lowerBound：第一个 >= target

lowerBound 返回第一个不小于 target 的下标，也就是 target 的左插入位置；所有元素都小于目标时返回 n。

/** 返回第一个满足 nums[index] >= target 的 index，范围为 [0, nums.length]。 */
int lowerBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

upperBound：第一个 > target

只需将谓词改为 nums[mid] > target。它返回 target 的右插入位置。

/** 返回第一个满足 nums[index] > target 的 index，范围为 [0, nums.length]。 */
int upperBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

找某个值：先找左边界，再验证

“精确查找”可以直接遇到相等就返回，但出现重复元素时返回位置不稳定。工程和刷题中更推荐复用 lowerBound：结果确定，还能无缝扩展到首个匹配位置。

/** 找 target 第一次出现的位置；不存在返回 -1。 */
int findFirstEqual(int[] nums, int target) {
    int index = lowerBound(nums, target);
    return index < nums.length && nums[index] == target ? index : -1;
}

/** 是否包含 target。 */
boolean contains(int[] nums, int target) {
    return findFirstEqual(nums, target) != -1;
}

前驱、后继与重复元素

给定升序数组，前驱是小于（或不大于）目标的最大元素，后继是大于（或不小于）目标的最小元素。不要把“严格”和“可相等”混淆。

/** 最大严格小于 target 的值；没有则返回 null。 */
Integer predecessorLessThan(int[] nums, int target) {
    int index = lowerBound(nums, target) - 1;
    return index >= 0 ? nums[index] : null;
}

/** 最小大于等于 target 的值；没有则返回 null。 */
Integer successorAtLeast(int[] nums, int target) {
    int index = lowerBound(nums, target);
    return index < nums.length ? nums[index] : null;
}

示例：找比 4 小的最大值

数组 nums = [1, 2, 4, 4, 4, 7, 9]，目标为 4：lowerBound(4) = 2，所以最大严格小于 4 的下标是 2 - 1 = 1，答案为 2。

若题目改成“找不大于 4 的最大值”，则用 upperBound(4) - 1 = 5 - 1 = 4，答案才是 4。

index:  0  1  2  3  4  5  6
nums : [1, 2, 4, 4, 4, 7, 9]
              ↑                 lowerBound(4) = 2：第一个 >= 4
           ↑                    最大 < 4：index = 1，值为 2
                    ↑           upperBound(4) = 5：第一个 > 4
                 ↑              最大 <= 4：index = 4，值为 4

过程图解

以 lowerBound([1, 2, 4, 4, 4, 7, 9], 4) 为例。谓词是 nums[i] >= 4，其真假分布为 F F T T T T T。

初始： [ left = 0,                 right = 7 )
       [ 1, 2, 4, 4, 4, 7, 9 ]
                  mid = 3，nums[3] = 4，满足，所以 right = 3

第 2 轮：[ left = 0, right = 3 )
         [ 1, 2, 4 | 4, 4, 7, 9 ]
            mid = 1，nums[1] = 2，不满足，所以 left = 2

第 3 轮：[ left = 2, right = 3 )
         [ 1, 2, 4 | 4, 4, 7, 9 ]
               mid = 2，nums[2] = 4，满足，所以 right = 2

结束： left == right == 2，答案为第一个满足谓词的位置。

mid 满足条件时保留 mid，因为它仍可能是最左答案；不满足时排除 mid，因为答案只能在右侧。这正是 right = mid 与 left = mid + 1 不对称的原因。

答案二分

很多题没有给出有序数组，却能判断“某个答案是否可行”。把答案本身当作二分对象：例如速度越大越容易按时完成、船容量越大越容易装完货。

模板：最小可行答案

适用于 false → true 的谓词。right 必须是一个已知可行的上界。

/** 在闭区间 [left, right] 中找最小的可行值；假设 right 一定可行。 */
int firstTrue(int left, int right) {
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

LeetCode 875：爱吃香蕉的珂珂

设每小时吃 speed 根。canFinish(speed) 随 speed 增大单调地从假变真，因此答案是最小可行速度。范围是 [1, max(piles)]。

int minEatingSpeed(int[] piles, int hours) {
    int left = 1;
    int right = 1;
    for (int pile : piles) {
        right = Math.max(right, pile);
    }

    while (left < right) {
        int speed = left + (right - left) / 2;
        if (canFinish(piles, hours, speed)) {
            right = speed;
        } else {
            left = speed + 1;
        }
    }
    return left;
}

boolean canFinish(int[] piles, int hours, int speed) {
    long needed = 0;
    for (int pile : piles) {
        // 等价于 ceil(pile / speed)，避免浮点数。
        needed += (pile + speed - 1) / speed;
    }
    return needed <= hours;
}

⚠️ needed 使用 long。即使每堆大小在 int 范围内，累计小时数仍可能溢出 int。

模板：最大可行答案

对于 true → false 的谓词，最稳妥的写法是仍找“第一个不可行”，最后减一：

// canPlace(x) 随 x 增大从 true 变为 false；right 是第一个已知不可行值。
int lastTrue(int left, int right) {
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canPlace(mid)) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left - 1;
}

LeetCode 题型地图

旋转数组：先识别有序半边

旋转数组不整体有序，但任意时刻至少有一半是有序的。以 LeetCode 33（元素互异）为例：

int searchRotated(int[] nums, int target) {
    int left = 0;
    int 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;
}

常见错误与快速参考卡

快速参考卡

提交前自检：搜索区间是什么？谓词是否单调？最终要第一个还是最后一个？mid 满足时是否仍可能是答案？边界返回值会不会越界？

参考资料

• CP-Algorithms — Binary Search
• 《算法导论（第 3 版）》— 第 2 章：算法基础
• 排序与搜索（二分查找的基础变体与排序上下文）