二分查找及其变体：lower bound、旋转数组、按答案搜索

1. 概述

二分查找是在有序数据上进行搜索的算法，时间复杂度为 O(log n)。思路非常简单，但实现容易出错：无限循环、边界错误（off-by-one）、计算 mid 时溢数。

本文从基础版本开始，介绍常见的变体：找到重复元素的首尾位置、统计出现次数、在旋转数组中查找、按答案进行二分搜索。读完这篇文章，你将拥有一套容错性强的实现框架，附带测试来验证。

2. 二分查找基础

假设你有一个已排序的产品价格数组，需要找到某个价格的位置：

public final class PriceSearch {

    public static int search(int[] prices, int target) {
        int lo = 0;
        int hi = prices.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prices[mid] == target) {
                return mid;
            }
            if (prices[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] prices = {100, 150, 200, 350, 500};
        System.out.println(search(prices, 350));
        System.out.println(search(prices, 300));
    }
}

解释：

• lo 和 hi 构成闭区间 [lo, hi]。这是 target 可能所在的区域。
• 条件 lo <= hi 表示当区间至少包含一个元素时循环继续运行。
• mid = lo + (hi - lo) / 2 避免溢数。写法 (lo + hi) / 2 会在 lo + hi 超过 Integer.MAX_VALUE 时溢出。等价的写法是 (lo + hi) >>> 1。
• 每一步后，我们将 mid 从区间中排除（mid + 1 或 mid - 1），所以区间总是在缩小，循环一定会终止。

结果：

3
-1

当数组不含重复元素，且你只需要知道“有或没有”时，这个版本足够。当有重复元素时，它返回重复组中的某个位置。通常这不是你想要的。

3. Lower bound 和 upper bound

两个最重要的变体是：

• lower bound：第一个满足 a[i] >= target 的下标。
• upper bound：第一个满足 a[i] > target 的下标。

两者都始终返回 [0, n] 范围内的下标，即使 target 不在数组中。这个下标正是插入位置，用于保持数组有序。

public final class Bounds {

    public static int lowerBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;              // 半开区间 [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    public static int upperBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

与基础版本的区别：

• 我们使用半开区间 [lo, hi)，所以 hi 初始化为 a.length，循环条件是 lo < hi。
• 当 a[mid] 满足“足够大”的条件时，我们赋值 hi = mid 而不是 mid - 1，因为 mid 仍可能是答案。
• 这两个函数只在 < 和 <= 的符号上不同。

用有重复元素的数组试验：

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Bounds.lowerBound(prices, 200)); // 1
System.out.println(Bounds.upperBound(prices, 200)); // 4
System.out.println(Bounds.lowerBound(prices, 300)); // 4
System.out.println(Bounds.lowerBound(prices, 900)); // 6

1
4
4
6

对于 300，结果 4 表示如果插入 300，它会排在 350 之前。对于 900，结果等于 n，意味着所有元素都比它小。

3.1. 首位置、末位置和出现次数

从上面两个函数，你可以直接推导出常见的问题：

public static int firstIndexOf(int[] a, int target) {
    int i = Bounds.lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

public static int lastIndexOf(int[] a, int target) {
    int i = Bounds.upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}

public static int count(int[] a, int target) {
    return Bounds.upperBound(a, target) - Bounds.lowerBound(a, target);
}

对于上面的 prices 和 target = 200，我们得到 firstIndexOf = 1、lastIndexOf = 3、count = 3。要记住的一点：在读取 a[i] 之前，始终检查边界 i < a.length（或 i >= 0）。

3.2. 统计范围内的元素

一个实际应用是统计价值在 [min, max] 范围内的订单数：

public static int countInRange(int[] sortedTotals, int min, int max) {
    return Bounds.upperBound(sortedTotals, max) - Bounds.lowerBound(sortedTotals, min);
}

对于 {100, 200, 200, 200, 350, 500} 和范围 [150, 400]，结果是多少？计算一下：upperBound(400) = 5、lowerBound(150) = 1，所以结果是 4。每次查询只需 O(log n)，无需遍历整个数组。

4. 在旋转数组中搜索

旋转数组是一个已排序的数组在某一点被“切断”并交换两半，例如 {40, 50, 60, 10, 20, 30}。这个数组不再完全递增，但围绕 mid 的至少一半仍然有序。我们依据这一点来决定往哪个方向走：

public static int searchRotated(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) {
            return mid;
        }
        if (a[lo] <= a[mid]) {                 // 左半部分有序
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               // 右半部分有序
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

解释：

• a[lo] <= a[mid] 表示区间 [lo, mid] 递增。如果 target 在这个区间的值范围内，我们向左收缩。否则，我们向右移动。
• 其余情况下，区间 [mid, hi] 递增，我们对称地推理。

System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 20));
System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 45));

4
-1

注意： 这个实现假设数组不含重复元素。对于像 {2, 2, 2, 3, 2} 这样的数组，条件 a[lo] <= a[mid] 无法区分哪一半有序。此时你需要额外处理 a[lo] == a[mid] 的情况，通过将 lo 增加一个单位，最坏时间复杂度变为 O(n)。

5. 按答案进行二分搜索

这是最强大的变体。它不在数组中搜索，而是寻找满足某个条件的最小值。适用的唯一条件是 predicate 必须单调：如果 x 满足，那么所有大于 x 的值也满足。换句话说，结果序列的形式是 false, false, ..., true, true。

我们编写一个通用函数：

import java.util.function.LongPredicate;

public final class AnswerSearch {

    /** [lo, hi] 中使 ok 返回 true 的最小值。假设 ok(hi) == true。 */
    public static long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

这个函数与 lowerBound 结构相同。实际上，lowerBound 只是 predicate a[i] >= target 的特例。

应用到实际问题中：仓库有一个固定顺序的包裹列表，需要在 maxDays 天内全部交付。每天车辆运送连续的包裹，总重量不超过车的承载容量。问最小承载能力是多少？

import java.util.Arrays;

public final class ShippingPlanner {

    public static long minCapacity(int[] weights, int maxDays) {
        long lo = Arrays.stream(weights).max().orElse(0);
        long hi = Arrays.stream(weights).asLongStream().sum();
        return AnswerSearch.firstTrue(lo, hi, cap -> canShip(weights, maxDays, cap));
    }

    static boolean canShip(int[] weights, int maxDays, long capacity) {
        int days = 1;
        long load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days <= maxDays;
    }

    public static void main(String[] args) {
        System.out.println(minCapacity(new int[]{3, 2, 2, 4, 1, 4}, 3));
    }
}

解释：

• lo 是最重的包裹，因为车必须能运送任何单个包裹。hi 是总重量，因为那时只需一天。因此 ok(hi) 肯定为真。
• canShip 模拟贪心算法：往车上装包裹，直到超载就换新的一天。承载能力越大，需要的天数越少，所以 predicate 是单调的。
• 总成本是 O(n · log(sum))，而不是逐一尝试每个承载能力。

6

对于承载能力 6，交付计划是 [3, 2]、[2, 4]、[1, 4]，正好 3 天。对于承载能力 5，需要 4 天，所以 5 不满足。

使用同样的模板可以解决许多其他问题：处理 batch 所需的最少线程数以满足时限、最小速率限制、整数的平方根。

6. 使用 Java 标准库

Java 已经内置了 Arrays.binarySearch 和 Collections.binarySearch。你需要清楚地理解它们的返回值：

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Arrays.binarySearch(prices, 350));
System.out.println(Arrays.binarySearch(prices, 300));

4
-5

• 找到时，函数返回元素的下标。
• 未找到时，函数返回 -(insertionPoint) - 1。这里插入位置是 4，所以结果是 -5。要重新获得插入位置，你计算 -(result) - 1。
• 当有重复元素时，文档不保证返回重复组中的哪个位置。如果需要首个或最后一个位置，请使用自己实现的 lowerBound/upperBound。

对于对象列表，你传递与已排序顺序匹配的 Comparator：

record Order(String id, long total) {}

List<Order> orders = List.of(
        new Order("A1", 120), new Order("B7", 300), new Order("C3", 450));
int idx = Collections.binarySearch(
        orders, new Order("?", 300), Comparator.comparingLong(Order::total));
System.out.println(idx); // 1

注意： Collections.binarySearch 在 LinkedList 上无法达到 O(log n)，因为按下标访问需要 O(n)。请使用 ArrayList 或数组。

7. 测试

添加 JUnit 5 和 AssertJ 依赖。如果项目使用 spring-boot-starter-test，两者已包含。

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.11.0</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

为边界情况编写测试。这是二分查找最容易出错的地方：

import org.junit.jupiter.api.Test;
import java.util.Random;
import java.util.stream.IntStream;
import static org.assertj.core.api.Assertions.assertThat;

class BoundsTest {

    private final int[] prices = {100, 200, 200, 200, 350, 500};

    @Test
    void lowerAndUpperBoundHandleDuplicates() {
        assertThat(Bounds.lowerBound(prices, 200)).isEqualTo(1);
        assertThat(Bounds.upperBound(prices, 200)).isEqualTo(4);
    }

    @Test
    void boundsReturnInsertionPointAtEdges() {
        assertThat(Bounds.lowerBound(prices, 50)).isZero();
        assertThat(Bounds.lowerBound(prices, 900)).isEqualTo(prices.length);
        assertThat(Bounds.lowerBound(new int[0], 1)).isZero();
    }

    @Test
    void lowerBoundMatchesLinearScan() {
        Random random = new Random(42);
        for (int round = 0; round < 1_000; round++) {
            int[] a = random.ints(random.nextInt(20), 0, 10).sorted().toArray();
            int target = random.nextInt(12) - 1;
            int expected = (int) IntStream.of(a).filter(x -> x < target).count();
            assertThat(Bounds.lowerBound(a, target)).isEqualTo(expected);
        }
    }

    @Test
    void minCapacityFindsSmallestFeasibleValue() {
        int[] weights = {3, 2, 2, 4, 1, 4};
        assertThat(ShippingPlanner.minCapacity(weights, 3)).isEqualTo(6);
        assertThat(ShippingPlanner.canShip(weights, 3, 5)).isFalse();
    }
}

测试 lowerBoundMatchesLinearScan 与 1000 个随机数组上的线性计数进行比较，包括空数组。这种对比测试比手工编写的几个例子更能捕捉 off-by-one 错误。

8. 常见错误和何时不应使用

常见错误：

• 混淆两种区间约定。 你初始化 hi = n（半开）但循环使用 while (lo <= hi) 并赋值 hi = mid - 1。结果是读取超出数组范围。选择一种约定并保持一致。
• 无限循环。 如果你写 lo = mid 配合 mid = (lo + hi) / 2，当 hi = lo + 1 时 mid == lo 区间无法缩小。如果真的需要 lo = mid，请向上舍入：mid = lo + (hi - lo + 1) / 2。
• 溢数，计算 mid 时或在按答案搜索时计算总和。对可能很大的值使用 long。
• Predicate 不单调。 二分查找仍会返回一个数字，但那个数字没有意义。在应用前证明单调性。

什么时候不应该使用二分查找：

• 数据未排序且只搜索几次。排序需要 O(n log n)，而线性搜索只需 O(n)。
• 你只需要用多次搜索检查“有或没有”。此时 HashSet 提供 O(1) 平均。
• 数据频繁变化，需要大量插入和删除。维持数组有序每次插入成本 O(n)。考虑 TreeMap/TreeSet，它们有 ceilingKey、floorKey、higherKey 等同于 lower bound 和 upper bound 的方法。
• 数组很小，只有几十个元素。线性遍历通常因缓存而同样快或更快，且代码更简单。

9. 总结

二分查找不仅仅是“在数组中查找元素”。掌握了带半开区间 [lo, hi) 的 lower bound 和 upper bound 后，你可以用几行代码解决首位置/末位置、计数和范围计数问题。旋转数组需要额外的步骤来确定哪一半有序。按答案搜索将这个技术扩展到任何有单调 predicate 的问题。

保持单一的区间约定，使用 >>> 或 lo + (hi - lo) / 2 避免溢数，且总是用线性搜索进行对比测试。这三个习惯消除了二分查找臭名昭著的大部分错误。