二分查找：每次排除一半

这一课你将能做到

1. 背出二分查找的循环不变量，不再被 left/right/mid 的 +1 -1 绕晕
2. 用两次二分写出「在排序数组中查找元素的第一个和最后一个位置」
3. 在旋转有序数组上判断哪一半仍然有序，完成 O(log n) 搜索

为什么要学

二分查找是效率最震撼的简单算法：在 100 万个有序数里找一个数，最多 20 次比较；10 亿个，也只要 30 次。O(log n) 的增长慢到可以视为「几乎和数据量无关」。

真实系统里它无处不在：数据库索引的 B+ 树查找是二分思想、Redis 跳表是分层二分、词典按拼音查词是二分。面试中二分题单独出现的概率中等，但**「搜索区间」「旋转数组」这类变体是区分死记模板和真正理解的试金石**——很多人能写出基础二分，一变体就死循环或漏解。本课帮你把边界彻底搞清楚。

先建立图像

核心只有一句话：每一步，区间里有一半可以被确定地排除。

[1, 3, 5, 7, 9, 11, 13]      找 9
 left        mid        right
            nums[mid]=7 < 9
 → 左半连同 mid 全部排除，left = mid + 1

写代码前先选定一种区间约定，全程不混用：

约定	初始	循环条件	缩界
左闭右闭 [left, right]	right = n-1	left <= right	命中后排除 mid：±1
左闭右开 [left, right)	right = n	left < right	right = mid

本课统一用左闭右闭，它直觉最强：区间表示「答案可能在的、包含两端的范围」。mid 一律写 left + (right - left) / 2，防止两数相加溢出。

跟着做

步骤 1：LeetCode 704「二分查找」（简单，模板）

class Solution {
    public int search(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;
            } else if (nums[mid] < target) {
                left = mid + 1;                 // mid 已查过，排除它
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

循环不变量：答案（如果存在）始终在 [left, right] 中。每次更新都维护这个事实，循环结束时区间为空、答案不存在。时间 O(log n)，空间 O(1)。

步骤 2：LeetCode 34「在排序数组中查找元素的第一个和最后一个位置」（中等）

给定升序数组（可能含重复值）和 target，返回它出现区间的起止下标，不存在返回 [-1,-1]。要求 O(log n)。

关键技巧：把「找第一个等于 target 的位置」转化成「找第一个 ≥ target 的位置（左边界）」；最后一个位置 = 「第一个 > target 的位置」减 1。写一个带 lower 参数的二分：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = lowerBound(nums, target);      // 第一个 >= target
        if (first == nums.length || nums[first] != target) {
            return new int[]{-1, -1};              // 连 >= target 的都没有，或那个位置不是 target
        }
        int afterLast = lowerBound(nums, target + 1); // 第一个 > target
        return new int[]{first, afterLast - 1};
    }

    // 返回第一个满足 nums[i] >= target 的下标；都小于 target 则返回 nums.length
    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // 注意这里用右开，答案可能是 n
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;    // mid 可能就是答案，不能排除
            }
        }
        return left;
    }
}

逐点讲：这是「左闭右开」约定的经典用法，因为答案允许取到 n。两次二分，时间 O(log n)，空间 O(1)。建议把 lowerBound 当作肌肉记忆背下来，大量二分变体都是它的包装。

步骤 3：LeetCode 33「搜索旋转排序数组」（中等）

升序数组在某点旋转过，如 [4,5,6,7,0,1,2]，找 target 的下标，找不到返回 -1。假设数组原本无重复。

难点：数组不再整体有序，不能直接比大小。但关键观察是——从中点切开，左右两半至少有一半是完全有序的：

• 若 nums[left] <= nums[mid]，左半有序。target 落在 [nums[left], nums[mid]) 内就去左半，否则去右半。
• 否则右半有序，同理判断 target 是否在右半的值域内。

class Solution {
    public int search(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;
    }
}

逐点讲：每轮仍排除一半，所以 O(log n)，空间 O(1)。注意判断有序用 <= 而非 <：当 left 和 mid 重合（区间只剩两个元素）时，那「一半」也必须被认作有序。

讲清楚要点

1. 先定区间约定，再写缩界：闭区间配 <= 和 ±1；半开配 < 和 right=mid。混用是死循环和漏解的根源。
2. 找边界用 lowerBound 思想：把「等于谁」改成「第一个满足不等式的位置」，重复值问题立刻规整。
3. 旋转数组的题眼是「判断哪半有序」：不是比较 target 和 mid，而是先判断 mid 两侧的结构，再用值域决定去向。
4. 防溢出写 left + (right-left)/2：大数组下 (left+right) 可能超过 int 上限。
5. 二分的输入前提是「可随机访问且有单调性」：数组满足，链表不适合（取中点就要 O(n)）。

你可能会懵的地方

• 为什么有时死循环？ 缩界没有真正排除 mid。比如半开区间里写了 right = mid + 1，或闭区间里命中不了时 left 只走到 mid，区间不再缩小。检查：每次迭代 right-left 是否严格变小。

• 34 题为什么用 target + 1 不会出错？溢出怎么办？ 整数范围内 target 是 int，本题数据也是 int，target = Integer.MAX_VALUE 时 +1 溢出成负数，lowerBound 会返回 0，答案恰好仍正确（最后位置 = n-1 时依赖具体数据）。更稳妥的工程写法是单独写「第一个 > target」的二分，逻辑同构，面试可提及这个细节。

• 旋转数组里 nums[left] <= nums[mid] 的等号为什么重要？ 当区间只剩两个元素，left==mid。不加等号会把这个有序的左半误判为「右半有序」，值域判断全错。

• 数组有重复值时旋转搜索（LeetCode 81）怎么办？ 无法靠比较判断哪半有序时（nums[left]==nums[mid]），把 left 收缩一格：left++，退化成最坏 O(n)，平均仍 O(log n)。

• 二分一定要递归吗？ 不需要，迭代写法 O(1) 空间、没有递归栈开销，是面试首选；递归二分只是教学上更对称。

错法对照

错法	问题	正解
(left + right) / 2	大下标相加整数溢出	left + (right - left) / 2
闭区间缩界不排除 mid	可能死循环	left = mid+1 / right = mid-1
lowerBound 里写 right = mid - 1	把答案本身排除了	满足条件时 right = mid
旋转数组直接比 target 与 mid	忽略整体无序，结论不可靠	先判断哪一半有序再定值域
判断左半有序用 <	left==mid 时误判	用 <=

卡点急救

1. 怀疑死循环：把每轮的 left/right 写在纸上，若连续两轮相同，就是缩界没排除 mid，回到区间约定检查。
2. 区间题差一错误（off-by-one）：别靠感觉改数字试。明确你的区间是「包含 right」还是「不包含」，所有更新都从这个定义推导。
3. 旋转数组理不清：先背一句「左端点 ≤ 中点 → 左半有序」，然后只问「target 在不在这个有序半段的值域里」，在则进、不在则去另一半。

面试常问

• 二分查找的时间复杂度为什么是 O(log n)？能优化到 O(1) 吗？ 每轮区间减半，需要 log₂n 轮才能从 n 缩到 0；每次操作 O(1)，所以 O(log n)。有序数组的查找这已是最优——任何基于比较的查找下界都是 O(log n)。哈希查找期望 O(1)，但不支持范围查询和有序遍历，各有适用场景。

• 如何在排序数组中统计 target 出现次数？ 就是 34 题：最后位置 - 第一个位置 + 1。两次 lowerBound，O(log n)，比遍历计数 O(n) 快。

• 求 x 的平方根（整数部分）怎么做？ 在 [0, x] 上二分，条件换成 mid <= x/mid（用除法防乘法溢出），找最大满足者。这是「二分答案」类型——对单调的判定条件直接二分可行解，后续优化题常见。

自测三问

1. 左闭右闭约定下，循环条件和缩界分别是什么？为什么？
2. lowerBound 返回 n 代表什么？34 题如何用它判断 target 不存在？
3. 旋转数组每轮先判断什么？为什么必须先判断「哪半有序」？

小结一句话

二分的灵魂不是 mid，而是「循环不变量 + 确定地排除一半」：边界题靠 lowerBound，旋转题先认有序半段，所有 ±1 都从区间定义推出。

延伸

• 巩固练习：LeetCode 35 搜索插入位置、LeetCode 81 搜索旋转排序数组 II、LeetCode 69 x 的平方根
• 在本站在线判题平台验证你的二分代码，重点测试单元素、两元素、target 在端点的用例
• 下一课预告：滑动窗口——双指针的连续区间特化版，解决无重复最长子串与最小覆盖子串