专题 04二分查找

4.1二分的本质：单调性上的折半

多数初学者把二分理解成「在有序数组里找一个数」。这个理解太窄了，导致一遇到变形就懵。 真正的本质是：

为什么说「不只是有序数组」

例子（先不写代码，建立直觉）：

• 有序数组找数：下标空间单调，nums[mid] 与 target 比大小就能判断往哪走。
• 找「第一个 ≥ target 的位置」：「某位置及之后都 ≥ target」这个性质，随下标增大从假变真，是单调的——也能二分。
• 答案在 [1, n] 里、且「mid 满足条件 → 答案 ≤ mid」：比如「最少切几刀」「最小速度」，这也是单调的，能二分答案（叫「二分答案」技巧）。

核心判断：拿到题先问——「我要求的东西，能不能排成一列，使得『越往一边越满足某条件』？」 能，就可以二分；不能（比如答案空间乱跳），二分就用不了。

4.2三种边界写法，背一种就够

二分最容易乱的就是「区间怎么定义、循环条件写 <= 还是 <、mid 加减 1 怎么配」。 其实三种写法都等价，挑一种背熟即可。本站统一用左闭右闭。

写法一（本站主推）：左闭右闭 while (left <= right)

初始 left = 0, right = n - 1，区间 [left, right] 两端都「包含」。因为包含右端，循环条件用 <=（只剩一个元素时也还要查）； 每次缩小都 left = mid + 1 或 right = mid - 1（mid 已查过，下次不再包含）。

int left = 0, right = n - 1;   // [left, right] 闭区间
while (left <= right) {        // 区间非空（含单元素）
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
}

写法二：左闭右开 while (left < right)

初始 right = n（开区间，不含 n），循环条件 <（左右相等时区间已空，停）。 缩小右边界用 right = mid（因为 right 本就不含，mid 可能是答案，不能 -1）。常用于「找左边界」模板。

int left = 0, right = n;        // [left, right) 左闭右开
while (left < right) {
    int mid = left + (right - left) / 2;   // 注意：这种写法 mid 取下整偏左
    if (nums[mid] >= target) right = mid;  // 含 mid
    else left = mid + 1;
}

写法三：找左/右边界的专门模板

就是 4.5 节要用的：把「== 就返回」改成「== 也继续逼向边界」。找左边界时遇到 nums[mid] >= target 一律 right = mid - 1（往左逼）； 找右边界时遇到 nums[mid] <= target 一律 left = mid + 1（往右逼）。循环结束后，left / right 恰好停在边界上。

4.3二分查找（简单，力扣 704）

简单 核心：左闭右闭主模板

题意：给定一个升序数组 nums 和目标值 target，若找到返回其下标，否则返回 -1。 例：nums = [-1,0,3,5,9,12], target = 9 → 返回 4；target = 2 → 返回 -1。

思路推导

第一步，为什么能二分。数组升序，下标空间单调：nums[mid] 比 target 大，说明目标只可能在左边；小则在右边。 每次比较能砍掉一半，O(log n)。

第二步，套主模板。左闭右闭区间，mid 用 left + (right - left) / 2（防溢出写法，见 4.7 节）。 nums[mid] == target 直接返回；< target 目标在右半，left = mid + 1；否则在左半，right = mid - 1。

第三步，退出循环意味着没找到。当 left > right，说明「还可能存在 target 的区间」已空，返回 -1。注意这里没有额外特判， 空数组 right = -1 时循环条件 left <= right 直接为假，安全返回 -1。

参考代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;    // 左闭右闭区间 [left, right]
        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;                 // 目标在左半，mid 已查剔除
        }
        return -1;                                // 区间空了还没找到
    }
}

复杂度

O(log n) 时间（每次砍半），O(1) 空间。这是所有二分题的根模板。

4.4搜索插入位置（简单，力扣 35）

简单 核心：找第一个 ≥ target 的位置

题意：给定升序数组 nums 和 target，若 target 存在返回其下标； 若不存在，返回它应该被插入的位置（插入后数组仍升序）。 例：nums = [1,3,5,6], target = 5 → 2；target = 2 → 1；target = 7 → 4。

思路推导

第一步，把问题翻译成二分。「插入位置」=「第一个 ≥ target 的下标」。如果 target 在数组里，这个位置恰好是它自己； 如果不在，它就是「所有比 target 小的元素之后」的位置。两者用同一个二分就能拿到。

第二步，复用主模板，只改返回。还是左闭右闭二分；找到相等直接返回（插入位置就是它自己）。 关键是没找到时：循环结束时 left > right，此时 left 恰好指向「第一个大于 target 的位置」——正是插入点。 所以直接 return left; 即可，不用任何额外逻辑。

第三步，为什么 left 就是插入点（直觉证明）。循环过程中，left 左边永远是「已确定 < target」的区域，right 右边永远是「已确定 > target」的区域。 当两者交错（left 越过 right），left 落在「> target 区域」的最左端，也就是该插入处。 可以拿 target = 7 推：全程 nums[mid] < 7，left 一直右移到 n，返回 n（插末尾）✓。

参考代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, 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;
            else right = mid - 1;
        }
        return left;   // 没找到：left 停在「第一个大于 target」处，即插入位置
    }
}

复杂度

O(log n) 时间，O(1) 空间。本题是「左边界模板」的简化版（相等即返回，不等时 left 自然落在边界）。

4.5在排序数组中查找元素的第一个和最后一个位置（中等，力扣 34）

中等 核心：左右边界模板组合

题意：给定升序且可能含重复的数组 nums 和 target， 返回 target 出现的起始和结束下标（闭区间）；若未出现返回 [-1, -1]。 例：nums = [5,7,7,8,8,10], target = 8 → [3, 4]；target = 6 → [-1, -1]。

思路推导

第一步，暴力 vs 二分。线性扫描 O(n)；但数组有序，重复元素必相邻，可以用两次二分分别定位「最左」和「最右」。

第二步，左边界模板。目标是「第一个 ≥ target 的位置」。把 704 的 == 就返回 改成「nums[mid] >= target 时也往左逼」： if (nums[mid] >= target) right = mid - 1; else left = mid + 1;。循环结束后 left 就是第一个 ≥ target 的下标。 （它等于 target 才有效，否则说明数组里没有 target。）

第三步，右边界模板。目标是「最后一个 ≤ target 的位置」。对称地：if (nums[mid] <= target) left = mid + 1; else right = mid - 1;。 循环结束后 right 就是最后一个 ≤ target 的下标。

第四步，组合 + 判空。先求左边界 start；若 start 越界或 nums[start] != target，直接返回 [-1,-1]； 否则求右边界 end，返回 [start, end]。两个子函数都复用左闭右闭骨架，区别只在「== 时往哪逼」。

参考代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = leftBound(nums, target);
        // start 越界 或 该位置不是 target → 说明数组里没有 target
        if (start == nums.length || nums[start] != target) return new int[]{-1, -1};
        int end = rightBound(nums, target);
        return new int[]{start, end};
    }
    // 第一个 >= target 的位置
    int leftBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) right = mid - 1; // 找到或偏大，继续往左逼
            else left = mid + 1;
        }
        return left;
    }
    // 最后一个 <= target 的位置
    int rightBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) left = mid + 1;  // 找到或偏小，继续往右逼
            else right = mid - 1;
        }
        return right;
    }
}

复杂度

O(log n) 时间（两次二分），O(1) 空间。这是「边界模板」的标准组合，面试高频。

4.6搜索旋转排序数组（中等，力扣 33）

中等 核心：半边有序的判断法

题意：一个原本升序、但在某个未知下标处被「旋转」过的数组（例如 [4,5,6,7,0,1,2]）， 无重复元素。在 O(log n) 内找出 target 的下标，找不到返回 -1。 例：nums = [4,5,6,7,0,1,2], target = 0 → 返回 4。

思路推导

第一步，普通二分为什么不行。数组整体不升序（中间会「断」），直接比 nums[mid] 和 target 不能判断往哪走—— 因为不知道 target 在断点的哪一侧。

第二步，关键性质——至少有一半是有序的。取 mid 后，区间被分成 [left, mid] 和 [mid, right] 两半。 因为只旋转了一次，这两半中必有一半是完全升序的。判断方法：若 nums[left] <= nums[mid]，说明左半 [left, mid] 没越过断点、是有序的；否则断点在左半、右半有序。

第三步，在有序的那一半里判断 target 在不在。若左半有序： 看 target 是否落在 [nums[left], nums[mid]) 范围内——在，就只在左半继续二分（right = mid - 1）； 不在，target 必在右半（left = mid + 1）。右半有序时对称处理。

第四步，为什么能砍掉一半。每一轮我们都确定了一整半是有序的，并在其中用「范围判断」决定丢弃哪一整半，所以每轮仍砍半，保持 O(log n)。

参考代码

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {            // 左半 [left, mid] 有序
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;                  // target 在左半范围内
                } else {
                    left = mid + 1;                   // 否则在右半
                }
            } else {                                   // 右半 [mid, right] 有序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;                   // target 在右半范围内
                } else {
                    right = mid - 1;                  // 否则在左半
                }
            }
        }
        return -1;
    }
}

复杂度

O(log n) 时间（每轮砍半），O(1) 空间。本题把「二分本质」体现得最充分：数组不整体单调，但局部单调就够用。

4.7本专题常见坑：死循环

4.8自测题