Leetcode刷题——二分查找

二分查找框架

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)

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
    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:
            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(右边界)

二分查找(简单)

来自算法小抄

找一个数

class Solution:
    def search(self, nums, target):
        left, right = 0, 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
s = Solution()
s.search([-1,0,3,5,9,12],9)
s.search([-1,0,3,5,9,12],2)

在排序数组中查找元素的第一个和最后一个位置(中等)

来自算法小抄

找左边界和右边界

class Solution:
    def searchRange(self, nums, target):
        # 分别找左右边界
        # 找左边界
        def binnary_search_left(nums, target):
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    right = mid
                elif nums[mid] > target:
                    right = mid
                elif nums[mid] < target:
                    left = mid + 1
            return left
        # 找右边界
        def binnary_search_right(nums, target):
            left, right = 0, len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid
                elif nums[mid] < target:
                    left = mid + 1
            return left - 1
    
        left,right = binnary_search_left(nums, target),binnary_search_right(nums, target)
        return [-1,-1] if left > right else [left,right]
        
s = Solution()
s.searchRange([5,7,7,8,8,10],6)
s.searchRange([5,7,7,8,8,10],8)
s.searchRange([],0)

搜索二维矩阵(中等)

class Solution:
    def searchMatrix(self, matrix, target):
        # 找左区间
        def binnary_search_left(nums,target):
            left,right = 0,len(nums)
            while left < right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    right = mid
                elif nums[mid] > target:
                    right = mid
                elif nums[mid] < target:
                    left = mid + 1
            return left
        def binnary_search(nums,target):
            left,right = 0,len(nums)-1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    return True
                elif nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
            return False
        if matrix == [] or matrix == [[]]: return False
        nums = [i[0] for i in matrix]
        row = binnary_search_left(nums,target)
        if row >= len(matrix) or matrix[row][0] > target: row -= 1
        return binnary_search(matrix[row],target)
s = Solution()
s.searchMatrix([[1],[3]],1)
s.searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]],11)
s.searchMatrix([[1]],1)

搜索二维矩阵II(中等)

逐行二分搜索

class Solution:
    def searchMatrix(self, matrix, target):
        def binnary_search(nums,target):
            left,right = 0,len(nums)-1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    return True
                elif nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
            return False
        res = False
        for i in range(len(matrix)):
            res = res or binnary_search(matrix[i],target)
        return res
s = Solution()
s.searchMatrix([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],20)

发表评论