力扣hot100_二分查找(1)_python版本

一、二分查找（开区间写法）

1. 如果找不到，返回的right是该插入的位置
2. 如果找到，是返回第一个等于target的位置

def binary_search(nums, target):
    left, right = -1, len(nums)
    while left+1 < right:  
        # 循环不变量
        # nums[left] < target
        # nums[right] >= target
        mid  = (left+right) // 2
        if nums[mid] < target:  # 循环不变量对齐
            left = mid
        else:
            right = mid
    return right

二、35. 搜索插入位置

• 思路：
  标准的二分查找的
• 代码：

def binary_search(nums, target):
    left, right = -1, len(nums)
    while left+1 < right:  
        # 循环不变量
        # nums[left] <right
        # nums[right] >= right
        mid  = (left+right) // 2
        if nums[mid] < target:  # 循环不变量对齐
            left = mid
        else:
            right = mid
    return right

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return binary_search(nums, target)

三、74. 搜索二维矩阵

• 思路1：
  这道题归到二分查找是因为，可以将每一行头尾相连得到一个有序的数组，然后使用二分查找。
• 思路2：
  直接使用排除法。
• 代码：

# 1.排除法
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        raw_tag = -1
        for i in range(m):
            if matrix[i][-1]==target:
                return True
            elif matrix[i][-1] > target:
                raw_tag = i
                break
            else:
                pass
        if raw_tag == -1:
            return False
        for j in matrix[raw_tag]:
            if target == j:
                return True
        return False
        
# 2.二分查找
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = -1, m * n
        while left + 1 < right:
            mid = (left + right) // 2
            x = matrix[mid // n][mid % n]
            if x == target:
                return True
            if x < target:
                left = mid
            else:
                right = mid
        return False

四、34. 在排序数组中查找元素的第一个和最后一个位置

• 思路：
  复用二分查找（二分查找是返回等于target的第一个位置）
• 代码：

def binary_search(nums, target):
    left, right = -1, len(nums)
    while left+1 < right:  
        # 循环不变量
        # nums[left] < target
        # nums[right] >= target
        mid  = (left+right) // 2
        if nums[mid] < target:  # 循环不变量对齐
            left = mid
        else:
            right = mid
    return right
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = self.binary_search(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        # 如果 start 存在，那么 end 必定存在
        end = self.lower_bound(nums, target + 1) - 1
        return [start, end]