二分查找

左右开闭

参考

开闭与 while 的条件和 left 与 right 的转移有关.

当左右都闭, 取值范围即为 [left, right], 因此 while 即使在 left == right 时也可以继续执行; 但是在左开右闭时, 取值范围为 [left, right), 因此 while 在 left == right 时就应该停止.

闭的一侧, while 循环后始终保持闭, 因此 left = mid + 1; 开的一侧, while 循环后始终保持开, 因此 right = mid.

left = 0, right = 1. 若 mid = 0, 左开右闭会有可能 left = mid = 0 陷入死循环, 因此 mid = left + (right - left) // 2 + 1; 若 mid = 1, 左闭右开会有可能 right = mid = 1 陷入死循环, 因此 mid = left + (right - left) // 2.

左闭右闭

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

左闭右开

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

左开右闭

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

寻找左右边界

参考

寻找左边界

对于左闭右闭的情形, 左边界相当于寻找第一个大于等于 target 的元素, 因此当 nums[mid] == target 时, right = mid - 1 尽量往左走.

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

寻找右边界

对于左闭右闭的情形, 右边界相当于寻找最后一个小于等于 target 的元素, 因此当 nums[mid] == target 时, left = mid + 1 尽量往右走.

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