二分查找边界问题完整笔记

📌 核心概念

边界定义

• 左边界：第一个等于 target 的位置
• 右边界：最后一个等于 target 的下一个位置（开区间）
• 有效区间：[左边界, 右边界) 包含所有等于 target 的元素

🔍 右边界查找算法

代码实现

// 二分查找，寻找target的右边界（不包括target）
int getRightBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int rightBorder = -2; // 记录没有被赋值的情况
  
    while (left <= right) {
        int middle = left + ((right - left) / 2);
      
        if (nums[middle] > target) {
            right = middle - 1; // target在左区间
        } else { 
            // 🔥 关键：nums[middle] <= target 时更新
            left = middle + 1;
            rightBorder = left; // 记录右边界
        }
    }
    return rightBorder;
}

⭐ 核心逻辑

1. 更新条件：nums[middle] <= target 时更新
2. 移动方向：向右搜索 (left = middle + 1)
3. 边界记录：rightBorder = left
4. 最终位置：第一个大于 target 的位置

执行过程

nums = [1,2,2,2,3], target = 2

初始: left=0, right=4, rightBorder=-2

1. middle=2, nums[2]=2 ≤ target
   → left=3, rightBorder=3

2. middle=3, nums[3]=2 ≤ target  
   → left=4, rightBorder=4

3. middle=4, nums[4]=3 > target
   → right=3, 循环结束

返回: rightBorder = 4
实际右边界: rightBorder - 1 = 3

🔍 左边界查找算法

代码实现

// 二分查找，寻找target的左边界（不包括target）
int getLeftBorder(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int leftBorder = -2; // 记录没有被赋值的情况
  
    while (left <= right) {
        int middle = left + ((right - left) / 2);
      
        if (nums[middle] >= target) {
            // 🔥 关键：nums[middle] >= target 时更新
            right = middle - 1;
            leftBorder = right; // 记录左边界
        } else {
            left = middle + 1;
        }
    }
    return leftBorder;
}

⭐ 核心逻辑

1. 更新条件：nums[middle] >= target 时更新
2. 移动方向：向左搜索 (right = middle - 1)
3. 边界记录：leftBorder = right
4. 最终位置：最后一个小于 target 的位置

执行过程

nums = [1,2,2,2,3], target = 2

初始: left=0, right=4, leftBorder=-2

1. middle=2, nums[2]=2 ≥ target
   → right=1, leftBorder=1

2. middle=0, nums[0]=1 < target
   → left=1

3. middle=1, nums[1]=2 ≥ target
   → right=0, leftBorder=0

返回: leftBorder = 0
实际左边界: leftBorder + 1 = 1

📊 对比总结

🎯 重要结论

目标值区间

int leftBorder = getLeftBorder(nums, target);
int rightBorder = getRightBorder(nums, target);

// target在数组中的完整区间
int start = leftBorder + 1;    // 第一个等于target的位置
int end = rightBorder - 1;     // 最后一个等于target的位置

// 有效区间: [start, end]

特殊情况处理

1. target不存在：start > end
2. target比所有元素小：边界值为初始值(-2)
3. target比所有元素大：左边界为数组长度

💡 记忆技巧

1. 右边界：遇到 ≤ 就向右，记录 left
2. 左边界：遇到 ≥ 就向左，记录 right
3. 实际边界：左边界要 +1，右边界要 -1

这样就能准确找到目标值的完整范围！