如何识别二分搜索中何时返回下界、上界与中间值？

当数组存在重复元素时，左边界（下界）是第一个等于目标值的索引，右边界（上界）是最后一个等于目标值的索引。核心区别在于找到目标值时的处理逻辑，以及循环结束后的边界验证。

左边界（下界）查找 #

逻辑：当nums[mid] == target时，不要直接返回mid，而是继续向左收缩范围，尝试找到更早出现的目标值。循环结束后需验证边界合法性。

代码示例：

def find_left_bound(nums, target):
    left = 0
    right = len(nums) - 1
    # 循环结束时left > right
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            # 等于或大于目标值时，向左收缩范围
            right = mid - 1
    # 循环结束后，left是第一个>=target的位置，需验证是否匹配目标值
    if left < len(nums) and nums[left] == target:
        return left
    return -1  # 数组中无目标值

关键要点：

• 只要nums[mid] >= target，就持续向左压缩搜索区间，确保不会错过更早出现的目标值
• 循环结束后必须验证left的合法性（不越界且值匹配），避免数组无目标值时返回错误索引

右边界（上界）查找 #

逻辑：当nums[mid] == target时，不要直接返回mid，而是继续向右收缩范围，尝试找到更晚出现的目标值。循环结束后同样需验证边界。

代码示例：

def find_right_bound(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] > target:
            right = mid - 1
        else:
            # 等于或小于目标值时，向右收缩范围
            left = mid + 1
    # 循环结束后，right是最后一个<=target的位置，需验证是否匹配目标值
    if right >= 0 and nums[right] == target:
        return right
    return -1  # 数组中无目标值

关键要点：

• 只要nums[mid] <= target，就持续向右压缩搜索区间，确保不会错过更晚出现的目标值
• 循环结束后验证right的合法性，避免数组无目标值时返回错误索引

核心区分点 #

普通二分查找找特定元素时，找到匹配值就返回，因为只需要任意一个匹配位置。但找上下界时，我们要的是极端位置，所以必须继续收缩区间直到搜索耗尽，再从边界位置反推结果。

快速判断技巧 #

• 找左边界：遇到等于目标值时向左走（right = mid -1），最终看left的位置
• 找右边界：遇到等于目标值时向右走（left = mid +1），最终看right的位置
• 统一用left <= right作为循环条件，减少不同循环逻辑带来的边界混淆

内容的提问来源于stack exchange，提问作者Shivansh Singh