二分查找：永远写不对？记住这个模板

二分查找是每个程序员都”会”但总写错的算法。

不是概念不懂——找中点、比大小、缩范围，谁都明白。问题在于：left <= right 还是 left < right？mid + 1 还是 mid？退出循环后要不要再检查一次？

死记硬背不可靠。真正的解法是理解每套模板背后的不变式，然后推导出所有边界条件。

为什么总写错

根本原因是区间语义不统一。

二分查找维护一个搜索区间，每次把目标缩小到区间的一半。但”区间”有两种表示方法：

• 闭区间 [left, right]：两端都可能是答案
• 左闭右开 [left, right)：right 是开边界，不在搜索范围内

这两种表示导致循环条件、mid 更新方式、终止后的处理全都不一样。混用就出 bug。

选一套，理解它，用到底。

模板一：闭区间 [left, right]

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;  // 闭区间 [left, right]

    while (left <= right) {  // 注意：<=，因为 left==right 时区间 [left,left] 仍有一个元素
        int mid = left + (right - left) / 2;  // 防止 (left+right) 溢出

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;   // target 在右半部分，[mid+1, right]
        } else {
            right = mid - 1;  // target 在左半部分，[left, mid-1]
        }
    }

    return -1;  // 未找到
}

关键推导：

• while (left <= right)：当 left > right 时区间为空，退出
• left = mid + 1：已经确认 nums[mid] < target，mid 不可能是答案，所以直接排除
• right = mid - 1：同理，mid 不可能是答案

适合：确定性查找（找到就返回，找不到返回 -1）

模板二：左闭右开 [left, right)

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size();  // 左闭右开 [left, right)

    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;  // target 在 [mid+1, right)
        } else {
            right = mid;     // target 在 [left, mid)，注意不是 mid-1
        }
    }

    return -1;
}

关键推导：

• right = nums.size()（而不是 size - 1），因为右端是开区间
• while (left < right)：left == right 时区间为空
• right = mid（不是 mid - 1）：因为右端是开区间，mid 本来就不在搜索范围内

这个模板在寻找边界时更自然，退出循环后 left 就是插入位置。

例题 1：标准二分（LeetCode 704）

给定升序整数数组 nums 和目标值 target，返回 target 的下标，不存在返回 -1。

直接套闭区间模板：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size() - 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 -1;
    }
};

例题 2：搜索插入位置（LeetCode 35）

给定排序数组和目标值，在数组中找到目标值并返回下标。如果不存在，返回它将被按顺序插入的位置。

这道题要找的是第一个 ≥ target 的位置，用左闭右开模板最顺手：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size();  // 插入位置可以是末尾，所以 right 取 size

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;   // target 在右边
            } else {
                right = mid;      // nums[mid] >= target，mid 可能就是答案，不排除
            }
        }

        // 循环结束时 left == right，就是插入位置
        return left;
    }
};

走一遍：nums = [1,3,5,6], target = 5

left=0, right=4
mid=2, nums[2]=5 >= 5, right=2
left=0, right=2
mid=1, nums[1]=3 < 5, left=2
left=2, right=2, 退出
返回 2 ✓

例题 3：查找第一个和最后一个位置（LeetCode 34）

在排序数组中找到目标值的第一个和最后一个位置，不存在返回 [-1, -1]。

这是二分的经典进阶：找左边界和右边界。

class Solution {
public:
    // 找第一个 >= target 的位置（左边界）
    int lowerBound(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;  // nums[mid] >= target，保留
        }
        return left;  // 第一个 >= target 的位置
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int first = lowerBound(nums, target);

        // 检查 first 是否有效
        if (first == (int)nums.size() || nums[first] != target) {
            return {-1, -1};
        }

        // 最后一个 target 的位置 = 第一个 > target 的位置 - 1
        int last = lowerBound(nums, target + 1) - 1;

        return {first, last};
    }
};

核心技巧：把找右边界转化为「找 target+1 的左边界然后 -1」，这样只需要一个 lowerBound 函数。

二分答案：不只是找元素

二分查找不只能用在数组上——任何具有单调性的答案空间都可以二分。

思路：不是在数组中找某个值，而是把「答案」本身作为搜索对象。

例：木材切割问题

给定 n 根木材的长度，需要切出 k 根长度为 L 的木材。找最大可行的 L。

暴力：枚举所有可能的 L（1 到 max），检查能否切出 k 根 → O(max × n)

二分答案：L 越大，能切出的根数越少（单调性）→ 对 L 进行二分

// 判断给定长度 L，能切出多少根
long long countPieces(vector<int>& logs, long long L) {
    long long count = 0;
    for (int log : logs) count += log / L;
    return count;
}

int maxLength(vector<int>& logs, int k) {
    long long left = 1, right = *max_element(logs.begin(), logs.end());
    long long ans = 0;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (countPieces(logs, mid) >= k) {
            ans = mid;       // mid 可行，尝试更大
            left = mid + 1;
        } else {
            right = mid - 1;  // mid 不可行，缩小
        }
    }

    return (int)ans;
}

二分答案的适用判断：

1. 答案在某个范围内
2. 存在单调性：答案越大（或越小），某个条件越难（或越容易）满足
3. 有一个 O(n) 或更快的 check(x) 函数

经典题型：最小化最大值、最大化最小值、K 个分组的最优切分。

两套模板对比

记忆口诀：左闭右开时，右端永远是「未来的 right」，所以 right = mid（不减 1）；退出后 left 就是答案位置，不需要额外检查。

总结

二分查找的边界问题有且只有一个解法：选定区间语义，严格遵守不变式。

• 闭区间：[left, right] 都可能是答案，循环条件 <=，更新时两端都要 ±1
• 左闭右开：right 是边界外，循环条件 <，更新 right 时直接赋 mid

选一套，理解为什么，剩下的推导就会水到渠成。