二分查找的边界艺术：LeetCode 34 题深度解析

一、问题引入：寻找区间的边界

本题要求在非递减数组中找到目标值的起始位置和结束位置，若不存在则返回 [-1, -1]。由于数组有序，常规二分只能定位任意目标位置，但本题需精确边界，这就需要利用 二分查找的二段性 设计条件。

二、二分的核心：二段性

二段性 指数组可被某个条件划分为两部分：一部分满足条件，另一部分不满足。例如：

• 左边界：数组分为「小于 target 的区间」和「大于等于 target 的区间」，分界点即左边界。
• 右边界：数组分为「小于等于 target 的区间」和「大于 target 的区间」，分界点即右边界。

利用二段性，我们可通过调整二分条件，让指针逐步逼近边界。

三、左边界的查找逻辑（找第一个 ≥ target 的位置）

以示例 nums = [5,7,7,8,8,10], target=8 为例，左边界是索引 3。

算法步骤：

1. 初始化：left=0, right=n-1（n 为数组长度）。
2. 循环条件：while (left < right)（当 left==right 时结束，此时即为结果）。
3. 计算中点：mid = left + (right - left) / 2（取左中位数，避免死循环）。
4. 条件判断：
   • 若 nums[mid] < target：mid 在「小于 target 区间」，左边界必在右侧，故 left = mid + 1。
   • 否则（nums[mid] ≥ target）：mid 可能在目标区间内，缩小右边界，故 right = mid。
5. 结果验证：循环结束后，检查 nums[left] 是否等于 target。若不等，说明目标不存在。

四、右边界的查找逻辑（找最后一个 ≤ target 的位置）

仍以示例为例，右边界是索引 4。

算法步骤：

1. 初始化：复用左边界的 left（优化性能），重置 right = n-1。
2. 循环条件：while (left < right)。
3. 计算中点：mid = left + (right - left + 1) / 2（取右中位数，避免死循环）。
4. 条件判断：
   • 若 nums[mid] > target：mid 在「大于 target 区间」，右边界必在左侧，故 right = mid - 1。
   • 否则（nums[mid] ≤ target）：mid 可能在目标区间内，扩大左边界，故 left = mid。
5. 结果直接使用：循环结束后，right 即为右边界（因左边界已验证存在，无需重复判断）。

五、代码实现

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        if (nums.empty()) return {-1, -1}; // 空数组直接返回
        
        // 1. 查找左边界
        int left = 0, right = nums.size() - 1;
        while (left < right) 
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
            {
                left = mid + 1; // 左半区不满足，右移左指针
            } else 
            {
                right = mid;    // 右半区可能满足，左移右指针
            }
        }
        int start = left; // 暂存左边界
        if (nums[start] != target) return {-1, -1}; // 目标不存在
        
        // 2. 查找右边界
        right = nums.size() - 1; // 重置右指针（左指针可复用start）
        while (left < right) 
        {
            int mid = left + (right - left + 1) / 2; // 右中位数
            if (nums[mid] > target) 
            {
                right = mid - 1; // 右半区不满足，左移右指针
            } else 
            {
                left = mid;      // 左半区可能满足，右移左指针
            }
        }
        int end = right;
        
        return {start, end};
    }
};

六、二分边界模板总结

记忆技巧：

• 左边界用 左中位数，右边界用 右中位数，避免死循环。
• 条件判断中，让需要 “跳出” 的区间移动指针（如左边界中，<target 的区间需跳出，故 left=mid+1）。

结语

二分查找的边界问题核心是 二段性的挖掘 和 指针收缩的细节处理。记住：边界的本质是二段性，模板的差异是中位数和条件的选择，理解这一点，二分问题将迎刃而解。