【弹力延伸】二分查找的本质：把搜索空间对折再对折

路飞的橡皮臂可以无限延伸，但二分查找的价值在于反其道而行——每次把可能的范围对折，指数速度缩小目标区间。一个长度 10 亿的有序数组，二分只需要 30 次比较。

二分查找写起来简单，但边界条件藏着无数 off-by-one 的坑。本文建立一套统一模板，彻底解决「到底用 < 还是 <=，mid+1 还是 mid」的问题。

---

一、统一模板

int l = 0, r = nums.length - 1;  // 闭区间 [l, r]
while (l <= r) {
    int mid = l + (r - l) / 2;   // 防止 (l+r) 溢出
    if (nums[mid] == target) return mid;
    if (nums[mid] < target)  l = mid + 1;
    else                     r = mid - 1;
}
return -1;

三个决策点，各有理由：

决策	选择	原因
初始 r	length - 1	搜索区间是闭区间 [0, n-1]，r 指向最后一个合法元素
循环条件	l <= r	当 l == r 时区间还有一个元素未检查，不能提前退出
缩小区间	l = mid+1 / r = mid-1	mid 已经被排除，下一轮不再考虑它

---

二、寻找左边界

当数组有重复元素，target 第一次出现的位置：

int leftBound(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target)       l = mid + 1;
        else if (nums[mid] > target)  r = mid - 1;
        else                          r = mid - 1; // 找到了，但继续向左收缩
    }
    // l 是第一个 >= target 的位置
    if (l >= nums.length || nums[l] != target) return -1;
    return l;
}

找到 target 时不立刻返回，而是把 r 往左推——把右侧的答案都排除，直到区间收缩到最左侧那个。

---

三、寻找右边界

int rightBound(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target)       l = mid + 1;
        else if (nums[mid] > target)  r = mid - 1;
        else                          l = mid + 1; // 找到了，但继续向右收缩
    }
    // r 是最后一个 <= target 的位置
    if (r < 0 || nums[r] != target) return -1;
    return r;
}

LeetCode 34 · 在排序数组中查找元素的第一个和最后一个位置，直接组合左右边界即可。

---

四、旋转有序数组

LeetCode 33 · 搜索旋转排序数组

数组在某点旋转后，虽然整体不是有序，但 mid 把它切成两半，至少有一半是有序的。

public int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        if (nums[l] <= nums[mid]) {            // 左半有序
            if (nums[l] <= target && target < nums[mid])
                r = mid - 1;
            else
                l = mid + 1;
        } else {                               // 右半有序
            if (nums[mid] < target && target <= nums[r])
                l = mid + 1;
            else
                r = mid - 1;
        }
    }
    return -1;
}

判断哪半有序：nums[l] <= nums[mid] 则左半有序，否则右半有序。确定有序的那半，再判断 target 是否落在其中，决定向哪侧缩减。

---

五、寻找峰值（LeetCode 162）

数组无重复元素，相邻元素不相等，找任意峰值（局部最大值）。

public int findPeakElement(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {                          // 注意：l < r，不是 l <= r
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[mid + 1]) r = mid;      // 峰在左侧（含mid）
        else                           l = mid + 1;  // 峰在右侧
    }
    return l;                                // l == r 时即为峰值
}

---

六、在答案空间上二分（最重要的变体）

二分不只能用在下标上，任何具有单调性的答案空间都可以二分。

模板：

能否用 mid 满足条件？
  能 → 缩小上界（尝试更小）
  不能 → 提高下界

LeetCode 875 · 爱吃香蕉的珂珂

珂珂以速度 k 吃香蕉，问最小的 k 使得 h 小时内吃完。速度越大越容易完成，答案有单调性，直接二分速度：

public int minEatingSpeed(int[] piles, int h) {
    int l = 1, r = Arrays.stream(piles).max().getAsInt();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (canFinish(piles, mid, h)) r = mid;  // 能完成，尝试更慢
        else                          l = mid + 1;
    }
    return l;
}

boolean canFinish(int[] piles, int speed, int h) {
    int hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;
    return hours <= h;
}

LeetCode 1011 · 在 D 天内送达包裹的能力

同样是答案二分：运载能力越大越容易在 D 天内送完，二分最小运载能力。

public int shipWithinDays(int[] weights, int days) {
    int l = Arrays.stream(weights).max().getAsInt(); // 至少能装最重的包裹
    int r = Arrays.stream(weights).sum();            // 最多一天送完
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (canShip(weights, mid, days)) r = mid;
        else                             l = mid + 1;
    }
    return l;
}

boolean canShip(int[] weights, int cap, int days) {
    int d = 1, cur = 0;
    for (int w : weights) {
        if (cur + w > cap) { d++; cur = 0; }
        cur += w;
    }
    return d <= days;
}

---

七、复杂度与边界速查

场景	时间	关键判断
标准二分	O(log n)	l <= r，mid ± 1
左/右边界	O(log n)	找到后不 return，继续收缩
旋转数组	O(log n)	先判断哪半有序
答案空间二分	O(n log ans)	写 check(mid) 函数

快速记忆边界选择：

• 搜索区间是 [l, r] 闭区间 → 循环用 l <= r，缩小用 ±1
• 搜索区间是 [l, r) 半开区间 → 循环用 l < r，右侧缩小用 mid（不含）

二分的精髓是：每次比较后，不只是排除一个元素，而是排除当前搜索空间的一半。这才是指数级压缩的来源，和路飞把橡皮臂一折再折、把攻击路径压缩到最短是同一件事。

---

下一站：风车村 · 【Gear 2】递归与回溯——暴力的优雅形态