Python刷题模板——二分查找

二分查找框架

def binarySearch(nums,target):
    left,right = 0,...
    while ...:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            ...
        elif nums[mid] < target:
            left = ...
        elif nums[mid] > target:
            right = ...
    return ...

查找一个数(不用记,直接画图就能写出来)

def binarySearch(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
        elif nums[mid] > target:
            right = mid - 1
    return -1

查找左边界,搜索区间[left,right)

记忆:left的都是+1

def left_bound(nums,target):
    if nums == []: return -1
    left,right = 0,len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right = mid 
        elif nums[mid] < target:
            left = mid + 1 
        elif nums[mid] > target:
            right = mid
    return left
    # 处理不存在target值
    # if (left == len(nums)) return -1
    # return nums[left] == target ? left : -1

查找右边界,搜索区间[left,right)

def right_bound(nums,target):
    if nums == []: return -1
    left,right = 0,len(nums)
    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
    return left - 1
    # 处理不存在target值
    # if (left == 0): return -1
    # return nums[left-1] == target ? left-1 : -1

使用python bisect模块

import bisect
​
bisect.bisect_left(nums,target) # 返回第一个target的坐标(左边界)
bisect.bisect_right(nums,target) # 返回最后一个target的坐标+1(右边界)

发表评论