二分查找：每次排除一半

这一课你将能做到

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;
    }
}