二分查找模板：边界、答案与变形一网打尽#

二分查找看起来简单，真正上手时却最容易在边界上翻车。与其每次都临场发挥，不如直接掌握一套稳定的模板。

⚡ 速记版模板#

// 模板用途：在有序数组中查找“第一个 >= target”的位置（可用于插入位置/左边界）
int left = 0; // 左边界：当前候选区间的起点（包含）
int right = nums.length; // 右边界：当前候选区间的终点（不包含），区间定义为 [left, right)
while (left < right) { // 只要区间里还有元素，就继续二分
    int mid = left + (right - left) / 2; // 取中点，避免 (left + right) 直接相加可能溢出
    if (nums[mid] < target) { // 中点值偏小，说明目标一定在右半区
        left = mid + 1; // 丢弃 [left, mid]，新区间变成 [mid + 1, right)
    } else { // 中点值大于等于 target，中点仍可能是答案
        right = mid; // 保留左半区，收缩为 [left, mid)
    }
}
return left; // 循环结束时 left == right，即第一个 >= target 的位置（插入位/左边界）

java

🎯 什么时候想到二分查找？#

当题目满足以下特征时，优先考虑二分：

数据本身有序
答案具有单调性
需要在一个区间里快速定位某个边界
题目问“最小的满足条件值”或“最大的满足条件值”

Hot 100 里的典型题目：

💡 核心不变量#

二分的关键不是背代码，而是维护好区间含义。

最常用的两种写法：

闭区间 [left, right]
- 初始化：left = 0, right = n - 1
- 循环条件：left <= right
- 适合精确查找某个值
左闭右开区间 [left, right)
- 初始化：left = 0, right = n
- 循环条件：left < right
- 适合找边界，更不容易写错

如果你没有强烈偏好，建议优先掌握“左闭右开”模板。

🚀 模板一：精确查找某个目标值#

class Solution {
    public int binarySearch(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 { // nums[mid] > target，中点偏大
                right = mid - 1; // 排除 mid
            }
        }

        return -1; // 区间耗尽仍未找到，返回不存在
    }
}

java

适用场景：

目标值是否存在
找到任意一个目标下标

🚀 模板二：找左边界#

这个模板特别适合：

第一个大于等于 target 的位置
第一个等于 target 的位置
搜索插入位置

class Solution {
    public int lowerBound(int[] nums, int target) {
        int left = 0; // 左边界（包含）
        int right = nums.length; // 右边界（不包含）

        while (left < right) { // 区间非空继续收缩
            int mid = left + (right - left) / 2; // 中点

            if (nums[mid] < target) { // 中点还没达到 target
                left = mid + 1; // 左边界右移，继续找第一个 >= target
            } else { // nums[mid] >= target，中点可能是答案
                right = mid; // 右边界收缩到 mid，保留 mid
            }
        }

        return left; // 返回第一个 >= target 的下标
    }
}

java

含义：返回数组中第一个大于等于 target 的位置。

🚀 模板三：找右边界#

class Solution {
    public int upperBound(int[] nums, int target) {
        int left = 0; // 左边界（包含）
        int right = nums.length; // 右边界（不包含）

        while (left < right) { // 区间非空则继续
            int mid = left + (right - left) / 2; // 中点

            if (nums[mid] <= target) { // 中点仍不大于 target
                left = mid + 1; // 继续向右找第一个 > target 的位置
            } else { // nums[mid] > target，中点可作为候选
                right = mid; // 收缩右边界，保留 mid
            }
        }

        return left; // 返回第一个 > target 的下标
    }
}

java

含义：返回数组中第一个大于 target 的位置。

如果要找最后一个等于 target 的位置，结果就是：

int rightIndex = upperBound(nums, target) - 1; // upperBound 给出第一个 > target，下标减 1 即最后一个 == target

java

🚀 模板四：答案二分#

有些题不是在数组里找数，而是在“答案空间”里找最优值。

例如：

最小满足条件值
最大可行值
某个容量、速度、时间的最优解

这类题的关键是定义一个 check(mid)：

若 check(mid) 为真，说明答案可能在左边，继续收缩右边界
若 check(mid) 为假，说明答案必须去右边

class Solution {
    public int binarySearchAnswer(int left, int right) {
        // 使用场景：答案空间具备单调性（例如“最小可行值”）
        // 参数含义：left/right 是答案的搜索范围，采用左闭右开或闭区间思路都可，但这里对应“找最小可行值”
        while (left < right) { // 区间还有多个候选答案时持续收缩
            int mid = left + (right - left) / 2; // 当前尝试的候选答案
            if (check(mid)) { // mid 可行：最优解可能在 mid 或其左侧
                right = mid; // 收缩右边界，继续逼近最小可行值
            } else { // mid 不可行：答案只能在右侧
                left = mid + 1; // 丢弃 mid 及其左侧
            }
        }
        return left; // 收敛后的 left 即最小可行答案
    }

    private boolean check(int value) {
        return true; // 判定函数：根据题意判断 value 是否满足条件（真实题目中需替换为具体逻辑）
    }
}

java

🧠 常见变体怎么套？#

1. 搜索插入位置#

直接套“找左边界”模板。

2. 查找某个数出现的左右边界#

左边界：lowerBound(nums, target)
右边界：upperBound(nums, target) - 1

3. 搜索旋转排序数组#

核心不是换模板，而是：

判断哪一半有序
再判断目标是否落在有序区间里

4. 寻找最小值#

利用旋转数组的结构，比较 mid 和 right 即可不断缩小区间。

⚠️ 易错点#

死循环
- 更新区间时别写成 left = mid 或 right = mid - 1 的混搭错误
- 先确定区间定义，再统一写法
边界越界
- 找边界时更推荐 right = nums.length
- 最终访问结果前先判断是否合法
中点溢出
- 用 left + (right - left) / 2
- 不要直接写 (left + right) / 2
左边界和右边界概念混淆
- lowerBound 是第一个 >= target
- upperBound 是第一个 > target

🎨 面试时怎么说#

你可以这样表达：

先说明区间定义
再说明循环条件
最后说明每次如何缩小范围

例如：

我这里维护的是左闭右开区间 [left, right)，每轮用 mid 判断目标应该保留在哪一半，直到区间收缩到一个点。

📌 一句话总结#

二分查找真正要记住的不是某一段代码，而是：

区间定义
单调性
边界收缩规则

只要这三点清楚，二分题就不会乱。