二分查找的边界问题与细节处理

题目描述：
给定一个有序数组（可能包含重复元素）和一个目标值，实现二分查找算法，不仅要判断目标值是否存在，还要精确找到其第一次出现和最后一次出现的位置（即查找左边界和右边界）。这是二分查找在实际工程中常见的变种，考察对循环条件、边界更新和终止条件的精确控制。

解题过程讲解：

步骤1：回顾标准二分查找
标准二分查找用于在有序数组中查找特定值是否存在：

1. 初始化左指针 left = 0，右指针 right = n-1（n为数组长度）。
2. 循环条件为 left <= right，计算中间位置 mid = left + (right - left) / 2（防止溢出）。
3. 若 nums[mid] == target，则找到目标，返回 mid。
4. 若 nums[mid] < target，说明目标在右半部分，更新 left = mid + 1。
5. 否则，更新 right = mid - 1。
6. 若循环结束未找到，返回 -1。

关键点：

• 循环条件 left <= right 确保搜索区间非空时持续查找。
• 每次更新 left 或 right 时跳过 mid，避免死循环。

步骤2：查找左边界（第一次出现的位置）
左边界定义为第一个等于 target 的元素索引，若不存在则返回 -1。实现时需要处理重复元素。

算法细节：

1. 初始化 left = 0，right = n（注意 right 初始为 n，而不是 n-1，原因后续解释）。
2. 循环条件为 left < right（不取等号）。
3. 计算 mid = left + (right - left) / 2。
4. 若 nums[mid] < target，说明目标在右侧，更新 left = mid + 1。
5. 若 nums[mid] >= target，说明目标在左侧或当前位置可能是左边界，更新 right = mid（注意不是 mid - 1）。
6. 循环结束时，left 和 right 相等，表示目标值应插入的位置（即第一个大于等于目标值的位置）。
7. 检查 left 是否越界或 nums[left] != target，若是则返回 -1，否则返回 left。

为什么这样设计：

• 循环条件 left < right 保证结束时 left == right，避免额外判断。
• 当 nums[mid] == target 时，不立即返回，而是让 right = mid，继续向左半部分收缩，直到找到第一个等于目标的位置。
• 初始化 right = n 使得搜索区间为左闭右开 [left, right)，与更新逻辑一致。

示例：数组 [1, 2, 2, 2, 3]，target = 2。
执行过程：

• 初始：left=0, right=5, mid=2（值2），更新 right=2。
• left=0, right=2, mid=1（值2），更新 right=1。
• left=0, right=1, mid=0（值1），更新 left=1。
• 循环结束，left=1，检查 nums[1]=2，返回 1。

步骤3：查找右边界（最后一次出现的位置）
右边界定义为最后一个等于 target 的元素索引。

算法细节：

1. 初始化 left = 0，right = n。
2. 循环条件 left < right。
3. 计算 mid = left + (right - left) / 2。
4. 若 nums[mid] <= target，说明目标在右侧或当前位置可能是右边界，更新 left = mid + 1。
5. 若 nums[mid] > target，更新 right = mid。
6. 循环结束时，left 为第一个大于目标的位置，因此右边界为 left - 1。
7. 检查 left - 1 是否越界或 nums[left - 1] != target，若是则返回 -1，否则返回 left - 1。

为什么这样设计：

• 当 nums[mid] == target 时，更新 left = mid + 1，向右推进，直到越过最后一个目标位置。
• 结束时 left 指向第一个大于目标的位置，故右边界为 left - 1。

示例：同样数组 [1, 2, 2, 2, 3]，target = 2。
执行过程：

• 初始：left=0, right=5, mid=2（值2），更新 left=3。
• left=3, right=5, mid=4（值3），更新 right=4。
• left=3, right=4, mid=3（值2），更新 left=4。
• 循环结束，left=4，右边界为 3，检查 nums[3]=2，返回 3。

步骤4：统一模板与易错点
上述方法可统一为“寻找左侧边界”和“寻找右侧边界”两个函数。
易错点总结：

1. 循环条件：使用 left < right 时，区间为左闭右开，更新逻辑需一致；若用 left <= right，区间为双闭，但处理边界时更易出错。
2. 更新逻辑：查找左边界时，nums[mid] >= target 则收缩右界；查找右边界时，nums[mid] <= target 则收缩左界。
3. 返回值检查：务必检查最终索引是否有效，以及对应值是否等于目标，避免数组全小于目标或全大于目标时返回错误索引。

代码框架（Python示例）：

def left_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    if left == len(nums) or nums[left] != target:
        return -1
    return left

def right_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid
    if left == 0 or nums[left - 1] != target:
        return -1
    return left - 1

步骤5：实际应用与变种
此问题可延伸至：

1. 寻找目标值插入位置（如 Python 的 bisect_left 和 bisect_right）。
2. 在旋转排序数组中搜索（结合边界判断调整搜索区间）。
3. 在数值连续但未知的范围内搜索（如猜数字游戏）。

掌握边界处理细节，能确保二分查找在各类场景下稳定工作，避免差一错误（off-by-one error）。