11.1 二分搜索与边界

前置：排序。本页从精确查找推进到左右边界，再讨论旋转数组；普通查找使用非降序 int[]；旋转查找要求原数组严格递增，再按任意分界点循环旋转。各函数不修改数组，要求非 null，也不在每次查询前重新验证排序；未满足前提时不保证结果。

二分搜索最容易错在混用区间模型，取中点反而只是其中一步。本页分成两类：

• 精确查找使用闭区间 [left, right]，循环条件是 left <= right；
• 边界查找使用左闭右开区间 [left, right)，循环条件是 left < right。

开始写代码前，先说清函数返回“某个等值位置”“第一个不小于目标的位置”，还是“第一个大于目标的位置”。这三个问题不能共用一句含糊的“找 target”。

一份可编译的边界实现

import java.util.Arrays;

public final class BinarySearchDemo {
    private BinarySearchDemo() {}

    static int search(int[] values, int target) {
        int left = 0;
        int right = values.length - 1;

        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (values[middle] == target) {
                return middle;
            }
            if (values[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return -1;
    }

    // 返回第一个 values[i] >= target 的 i；若不存在，返回 values.length。
    static int lowerBound(int[] values, int target) {
        int left = 0;
        int right = values.length;

        while (left < right) {
            int middle = left + (right - left) / 2;
            if (values[middle] < target) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        return left;
    }

    // 返回第一个 values[i] > target 的 i；若不存在，返回 values.length。
    static int upperBound(int[] values, int target) {
        int left = 0;
        int right = values.length;

        while (left < right) {
            int middle = left + (right - left) / 2;
            if (values[middle] <= target) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        return left;
    }

    static int searchRotatedDistinct(int[] values, int target) {
        int left = 0;
        int right = values.length - 1;

        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (values[middle] == target) {
                return middle;
            }

            if (values[left] <= values[middle]) {
                if (values[left] <= target && target < values[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            } else {
                if (values[middle] < target && target <= values[right]) {
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] values = {1, 2, 4, 4, 4, 5, 6};

        assert search(values, 4) >= 2 && search(values, 4) <= 4;
        assert search(values, 7) == -1;
        assert lowerBound(values, 4) == 2;
        assert upperBound(values, 4) == 5;
        assert lowerBound(values, 0) == 0;
        assert lowerBound(values, 7) == values.length;
        assert upperBound(new int[0], 3) == 0;

        int[] rotated = {4, 5, 6, 7, 0, 1, 2};
        assert searchRotatedDistinct(rotated, 0) == 4;
        assert searchRotatedDistinct(rotated, 3) == -1;

        System.out.println(Arrays.toString(values));
        System.out.println("4 的区间：[" + lowerBound(values, 4)
                + ", " + upperBound(values, 4) + ")");
    }
}

运行时要启用 Java 断言：

javac BinarySearchDemo.java
java -ea BinarySearchDemo

完整输出：

[1, 2, 4, 4, 4, 5, 6]
4 的区间：[2, 5)

其中 [2, 5) 表示三个 4 位于下标 2、3、4。精确查找只承诺返回某个匹配位置；若业务要统计重复值，应用两个边界之差：

count(target) = upperBound(values, target) - lowerBound(values, target)

用不变量检查收缩方向

lowerBound 的目标是第一个 >= target 的位置。循环中始终保持：

• [0, left) 的元素已经确定小于目标；
• [right, n) 的元素已经确定不小于目标；
• 未决区间是 [left, right)。

当 left == right 时，未决区间为空，交界处就是答案。即使目标小于全部元素、超过全部元素或数组为空，这个返回合同仍成立，不需要额外分支。

upperBound 只把判定从 < target 改成 <= target，因此返回第一个严格大于目标的位置。最后一个 <= target 的位置可写成 upperBound(...) - 1，但结果可能是 -1，调用方必须接受这个边界。

中点写成 left + (right - left) / 2，可避免 left + right 在 Java int 范围内溢出。这里数组下标非负且有 left <= right，所以差值也在 int 范围内。若换成可能横跨负数和正数的任意整数区间，right-left 本身也可能溢出，需要更宽类型。

旋转数组为什么仍能减半

严格递增数组按任意分界点循环旋转后，例如：

[0, 1, 2, 4, 5, 6, 7] -> [4, 5, 6, 7, 0, 1, 2]

每轮至少有一半仍严格有序。代码先判断左半是否有序，再检查目标是否落在该半的闭开范围内；否则转向另一半。

本页函数明确要求 key 互异。若允许大量重复值，values[left] == values[middle] == values[right] 时可能无法判断哪半有序，只能逐步缩边界，最坏时间会退化到 O(n)。不要在接口没有说明重复规则时照搬互异版本。

复杂度与适用边界

问题	时间	额外空间	前提
精确二分	O(log n)	O(1)	升序数组
lower / upper bound	O(log n)	O(1)	升序数组
旋转数组，key 互异	O(log n)	O(1)	严格递增数组按任意分界点循环旋转，可不旋转
旋转数组，允许重复	最坏 O(n)	O(1)	需要专门处理模糊区间

表中的对数界描述规模增长；空数组和单元素只做常数次检查。返回 n 的边界位置是合法插入点，却不是可读取的数组下标，必须先检查再访问。

数据若持续插入删除，维护有序数组本身可能需要 O(n) 移动；此时应把查询频率、更新频率和数据结构一起考虑。二分搜索只分析“已有随机访问有序序列上的定位”。

Java Arrays.binarySearch 未命中时返回 -(insertionPoint+1)，而本页 search 统一返回 -1。例如在 [1,2,4] 中找 3，插入点为 2，库方法返回 -3；由负结果 r 可用 -(r+1) 解码。命中重复值时也不保证返回第一个位置。详见 Java Arrays.binarySearch。

动手验证边界

1. 手算空数组、单元素数组和全部元素相等时的 lowerBound。
2. 用 lowerBound == upperBound 判断目标是否缺失，解释为什么成立。
3. 为旋转数组函数增加随机测试：先生成严格递增数组，再选择任意旋转点。
4. 若需求是“第一个等于 target 的位置”，怎样复用 lowerBound 并处理缺失？

二分搜索靠一份持续成立的区间不变量，而不只是一句“每次减半”。区间模型、收缩规则和返回合同三者一致，空数组、重复值和越界插入点就会自然落入同一套推理。

下一篇把定位对象从数字换成文本，进入 Rabin–Karp、KMP 与 Trie。再往后则用同样的“缩小问题”思路学习 分治。