第 11 章：搜索与字符串匹配 —— 二分搜索

---

元数据卡： 难度 进阶 | 前置 第 5 章（二叉树） | 关键词 二分搜索·边界条件·旋转数组·三分搜索 | 预计阅读 40 分钟

---

你的进度

你已经是排序大师了。但排序只是手段。想象一本记了十亿条排名笔记，要找「林间行者」。对半翻，再对半翻——30 次比较就够了。切换到现实：千万行日志中定位一次异常，从头读 O(n)，二分 O(log n)。

你的任务： 掌握二分搜索三种变体（标准、左边界、右边界），学会旋转数组中搜索，了解三分搜索。

---

标准二分搜索

每次取中间，排除一半。

// BinarySearch.java
public class BinarySearch {
    // 标准二分：找 target 在有序数组中的位置
    static int search(int[] a, int t) {
        int l = 0, r = a.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;  // 防溢出
            if (a[m] == t) return m;
            if (a[m] < t)  l = m + 1;
            else           r = m - 1;
        }
        return -1;
    }

    // 左边界：第一个 >= target 的位置
    static int lowerBound(int[] a, int t) {
        int l = 0, r = a.length;  // 左闭右开
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a[m] < t) l = m + 1;
            else          r = m;
        }
        return l;
    }

    // 右边界：最后一个 <= target 的位置
    static int upperBound(int[] a, int t) {
        int l = 0, r = a.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a[m] > t) r = m;
            else          l = m + 1;
        }
        return l - 1;  // l 停在第一个 > t 的位置
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 4, 4, 5, 6};
        System.out.println(search(arr, 7));        // 3
        System.out.println(search(arr, 10));       // -1
        System.out.println(lowerBound(arr, 4));    // 2
        System.out.println(lowerBound(arr, 7));    // 7
        System.out.println(upperBound(arr, 4));    // 4
        System.out.println(upperBound(arr, 5));    // 5
    }
}

javac BinarySearch.java && java BinarySearch
→ 3  -1  2  7  4  5

注意防溢出： Java 中 (l + r) / 2 在 l+r 超过 Integer.MAX_VALUE 时溢出为负数。永远用 l + (r - l) / 2。

版本	区间	循环	返回
标准	[l, r]	<=	m 或 -1
左边界	[l, r)	<	l
右边界	[l, r)	<	l - 1

右边界本质 = 先找第一个 > target 的位置再减一。

---

旋转数组中的二分

数组在未知点被旋转了：[0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]。总有一半严格有序。

// RotatedArraySearch.java
public class RotatedArraySearch {
    static int search(int[] a, int t) {
        int l = 0, r = a.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (a[m] == t) return m;

            if (a[l] <= a[m]) {             // 左半有序
                if (a[l] <= t && t < a[m]) r = m - 1;
                else                       l = m + 1;
            } else {                        // 右半有序
                if (a[m] < t && t <= a[r]) l = m + 1;
                else                       r = m - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(search(arr, 0));  // 4
        System.out.println(search(arr, 3));  // -1
    }
}

javac RotatedArraySearch.java && java RotatedArraySearch
→ 4
→ -1

---

附录：三分搜索（连续函数极值）

离散数组用二分就够了（一次比较排除一半，三分两次比较只排除 1/3）。但在连续单峰函数找极值时，三分有用。

// TernarySearch.java
public class TernarySearch {
    static double f(double x) { return -(x * x) + 5 * x + 10; }

    public static void main(String[] args) {
        double l = -10, r = 10, eps = 1e-7;
        while (r - l > eps) {
            double m1 = l + (r - l) / 3;
            double m2 = r - (r - l) / 3;
            if (f(m1) < f(m2)) l = m1;
            else               r = m2;
        }
        double maxX = (l + r) / 2;
        System.out.printf("x=%.4f f(x)=%.4f%n", maxX, f(maxX));
    }
}

javac TernarySearch.java && java TernarySearch
→ x=2.5000 f(x)=16.2500

---

常见陷阱

写二分本质是三个问题：区间模型、收缩规则、终止条件。混用就一定错。 每次先想清楚再下笔。

旅人笔记

二分搜索是"三分钟学会，一辈子写不完美"的算法。区间开闭一致，是二分的唯一真理。

---

下一步

二分解决有序序列中的定位。但如果数据是文本——在一段日志里找某个名字出现多少次？这是字符串匹配的领域。

→ 进入字符串匹配：Rabin-Karp 与 KMP

← 回到第 10 章：排序算法（下） | → 进入第 12 章：分治与回溯