二分搜索的几种变体

注意全部是闭区间搜索

1. 基础

left = 0
right = len(nums)-1     #[left, right]闭区间
while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] == target: 
        return mid
    elif nums[mid] < target: 
        left = mid + 1   
    elif nums[mid] > target:
        right = mid - 1     
return -1    # while终止时 left>right仍然没找到 返回-1

2. 寻找左侧边界

left = 0
right = 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   
    elif nums[mid] > target:
        right = mid - 1   
if left>=len(nums) or nums[left]!=target:
    return -1        # 越界 
return left

3. 寻找右侧边界

left = 0
right = 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   
    elif nums[mid] > target:
        right = mid - 1   
if right<0 or nums[right]!=target:
    return -1        # 越界 
return right