leetcode--二分查找模板总结(python3)

1、基本二分

def binarySearch(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:  #终止条件
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    return -1

思考：
为什么终止条件为 left <= right，因当 left == right，也就代表在一个元素中搜索，意味着 mid == left == right，当寻找到最后一个元素都无解时，则退出

基本二分的缺陷：
当nums中包含重复元素时 nums = [2,2,3,3]， 你无法控制你查到的是左侧的target还是右侧的target，进一步抽象也就是你无法控制target的边界。

2、 寻找左侧边界的二分搜索

def left_bound(nums, target):
    if len(nums) == 0: return -1
    left = 0
    right = len(nums) # 注意不同点

    while left < right: # 注意不同点
        mid = (left + right) //2
        if nums[mid] == target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid #注意不同点
    return left

思考：
终止条件为何不同了?
--因为搜索的区间[left, right] 变为了[left, right)
更新操作为何不同了?
--与上同理
最终返回的为什么是left?
--由于终止条件变为了left == right , 所以返回谁都无所谓
右侧边界呢？
--对照改变当nums[mid] == target成立时的更新操作与返回的条件即可

3、 寻找右侧边界的二分搜索

def right_bound(nums, target):
    if len(nums) == 0: return -1
    left = 0
    right = len(nums)

    while left < right: 
        mid = (left + right) //2
        if nums[mid] == target:
            left = mid + 1 #注意不同点
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid 
    return left - 1 #注意不同点

参考文献：
https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/er-fen-cha-zhao-xiang-jie