二分查找的 8 种变体：核心在于区间定义

一句话结论（30s）

二分查找 8 种变体的统一本质是「区间定义 + 相等时的收缩方向」——因为找「第一个」时相等也往左缩（right = mid - 1）、找「最后一个」时相等也往右扩（left = mid + 1），配合左闭右闭区间的 left <= right 退出条件，就能覆盖等于、第一个、最后一个、lower_bound、旋转数组等所有查找场景。

核心原理（2min）

经典二分：[left, right] 左闭右闭，while (left <= right)，mid = left + (right - left) / 2 防溢出。为什么是 left <= right 而不是 <？ 因为左闭右闭区间里 left == right 时仍有一个元素没检查，若写成 < 就会漏掉唯一一个候选位置。
找第一个：>= 时 right = mid - 1（找到了也往左缩），循环结束后 left 即答案。
找最后一个：<= 时 left = mid + 1（找到了也往右扩），循环结束后 right 即答案。
lower_bound（第一个 >= target）与「第一个等于」同构；upper_bound（第一个 > target）是 > 时 right = mid - 1。
旋转数组：每次二分后至少一段有序，判断 target 是否落在有序段内，决定去哪半找。

底层深入（5-10min）

经典二分（找等于 target）

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {  // [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 -1;
}

区间是 [left, right]（左闭右闭）。left <= right 是合法的，因为 left == right 时区间还有一个元素要检查。为什么不写 mid = (left + right) / 2？ 当 left + right 超过 int 上限会溢出变成负数，导致下标越界；写成 left + (right - left) / 2 就绕开了加法溢出。

💭 思考：看到什么信号该想到二分？——“有序数组 + 查找”是明牌，但更值得记的是：只要答案空间是”单调可分”的（比 target 小的在左、大的在右），就能二分。而 8 种变体看起来眼花，本质只有两件事要先定死：区间是左闭右闭还是左闭右开、相等时往哪边缩。把这两点定下来，while 条件、mid、返回值就都跟着确定，不会再写出死循环。

找第一个等于 target

int firstEqual(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;
    }
    // left 是第一个 ≥ target 的位置
    if (left < nums.length && nums[left] == target) return left;
    return -1;
}

>= 在相等时也往左缩——即使找到了 target，也继续收缩右边界，直到 left 指向第一个 target。

💭 思考：为什么找”第一个”要 >= 时也往左缩？——关键是想清楚”相等时不代表完事”：nums[mid] == target 只说明 mid 是其中一个，左边可能还藏着更靠前的 target。要拿到”最左”，就得在命中时也把右边界压到 mid - 1，逼着搜索区间持续左移，直到 left 停在第一个满足 >= target 的位置。把”找第一个”翻译成”找第一个 >= target”，问题就统一了。

找最后一个等于 target

int lastEqual(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;
    }
    if (right >= 0 && nums[right] == target) return right;
    return -1;
}

对称——<= 在相等时往右扩。

找第一个大于等于 target（lower_bound）

与”第一个等于 target”完全一样——left 就是答案。

旋转排序数组中的二分

int searchInRotated(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]) {  // 左半段有序
            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;
}

核心：每次二分后，至少有一段是有序的。判断 target 是否在有序段内 → 决定去哪半找。

💭 思考：旋转数组怎么还能用二分？——普通二分的前提是”整体有序”，旋转后整体无序了，但取 mid 后，mid 左右两半必有一半仍是有序的（nums[left] <= nums[mid] 判左半、否则右半）。于是二分退化成一招：先找出”哪半有序”，再判断 target 在不在那半的区间内，在就去、不在就去另一半。抓住”永远有一半有序”这个不变量，旋转数组就不神秘了。

章末提问

找”第一个等于 target”为什么是 >= 时 right = mid - 1，而不是相等就 return？ 结论：因为相等时不能直接返回，左边可能还有相同的 target；所以相等也继续往左缩，直到 left 越过所有候选，循环结束 left 就是最左位置。
二分查找的退出条件为什么和区间定义强绑定？ 结论：因为 left <= right 对应左闭右闭、left < right 对应左闭右开，区间定义错了循环就会漏元素或死循环；所有变体 bug 的根源几乎都是区间不统一。
旋转排序数组里怎么判断该去哪半边找？ 结论：每次二分后至少有一半是有序的，先判断 target 是否落在那段有序区间内，在就去那边、不在就去另一边；因为无序那一半内部也仍是旋转结构，递归处理即可。

二分查找通解

所有变体最终归结到同一条原则：mid 的计算方式和 left/right 的更新方式决定了找的是”最左”还是”最右”的 target。

变体	相等时的操作	返回值
firstEqual	`right = mid - 1`	left
lastEqual	`left = mid + 1`	right
lower_bound	`>=` 时 `right = mid - 1`	left
upper_bound	`>` 时 `right = mid - 1`	left

二分查找的8种变体——不只是找等于target