leetcode_problem-Binary_Search

Tony Cao2024-02-022024-10-29

常见的二分查找的方法

1. 二分查找昌需要确定target和middle的相对位置（如图）：

常见的方式是使用左闭右开的区间，符合python中数据的定义格式

lower_bound 返回最小的满足 nums[i] >= target 的 i
如果数组为空，或者所有数都 < target，则返回 len(nums)
要求 nums 是非递减，即 nums[i] <= nums[i + 1]

左闭右开区间写法（常用的写法，一般python中的range()函数也是左闭右开区间，应该使用统一的标准）

def lower_bound2(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)  # 左闭右开区间 [left, right)，取值的左右区间是否开闭，会影响二分中left，right的取值
    while left < right:  # 区间不为空， 当left==right时，则跳出循环，因为[left, left)或者[right, right)这样的区间是不存在的。        
        # 循环不变量：对应的是左开有闭的区间
        # nums[left-1] < target
        # nums[right] >= target
        mid = (left + right) // 2 	# mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right)
        elif nums[mid] > target:
            right = mid  # 范围缩小到 [left, mid)
        #---------------------------------
        # target无左右边界的写法
        elif nums[mid] == target: #此时找到target所在的位置
            return mid
        #---------------------------------
        # target有左右边界的写法
        # 如果nums中有多个target，要找到target的左右两侧边界的写法为：
        elif nums[mid] == target: #此时找到某个target，需要找到左边界的索引，此时应该移动右边界，当左右边界重合的时候，此时刚好是left==right，找到了target的左边界。让right==mid，因为右边是开区间
            right = mid
        elif nums[mid] == target: #此时找到某个target，需要找到右边界的索引，此时应该移动左边界，当左右边界重合的时候，此时刚好是left==right，找到了target的右边界。让left = mid + 1，因为左边界是闭区间
            left = mid + 1
        #-----------------------------
            
    return left  # 返回 left 还是 right 都行，因为循环结束后 left == right

闭区间写法

def lower_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    while left <= right:  # 区间不为空，返回left+1 > right的时候，tiao'chu
        # 循环不变量：
        # nums[left-1] < target
        # nums[right+1] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right]
        else:
            right = mid - 1  # 范围缩小到 [left, mid-1]
    return left

开区间写法

def lower_bound3(nums: List[int], target: int) -> int:
    left, right = -1, len(nums)  # 开区间 (left, right)
    while left + 1 < right:  # 区间不为空
        mid = (left + right) // 2
        # 循环不变量：
        # nums[left] < target
        # nums[right] >= target
        if nums[mid] < target:
            left = mid  # 范围缩小到 (mid, right)
        else:
            right = mid  # 范围缩小到 (left, mid)
    return right