hot100 -- 11.二分查找系列

1.搜索插入位置

问题：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

方法：二分查找（不断折半找，找不到时，left就是要插入的位置）

# 方法：二分查找（不断折半找，找不到时，left就是要插入的位置）
def SearchInsert(nums, target):left, right = 0, len(nums)-1while left <= right:                # 等号一定要加，否则会漏检目标值！！！mid = (left + right) // 2if nums[mid] == target:return midelif target < nums[mid]:right = mid-1else:left = mid+1return left

2.搜索二维矩阵

问题：

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

方法1：分步搜索

# 方法1：分步搜索（循环定位行 + 二分查找定位列，类似暴力解法，时间复杂度：O(m+logn)
def SearchMatrix(matrix, target):if target < matrix[0][0] or target > matrix[-1][-1]:return False# 行定位for row in range(len(matrix)):if target >= matrix[row][0] and target <= matrix[row][-1]:# 列定位left, right = 0, len(matrix[0])while left <= right:mid = (left + right)//2if target == matrix[row][mid]:return Trueelif target > matrix[row][mid]:left = mid + 1else:right = mid - 1return False

方法2：二维二分查找（推荐）

# 方法2：二维二分查找（分别二分查找行和列，时间复杂度O(logm + logn)
def SearchMatrix(matrix, target):if target < matrix[0][0] or target > matrix[-1][-1]:return Falsetop, bottom = 0, len(matrix)-1# 行定位while top <= bottom:mid_row = (top + bottom) // 2# 列定位（找到区间范围，只可能在该区间了，开始列定位：有则返回True，无则直接返回False）if matrix[mid_row][0] <= target <= matrix[mid_row][-1]:left, right = 0, len(matrix[0])-1while left <= right:mid_col = (left + right)//2if target == matrix[mid_row][mid_col]:return Trueelif target > matrix[mid_row][mid_col]:left = mid_col + 1else:right = mid_col - 1return False            # 该区间找不到，直接返回Falseelif target > matrix[mid_row][0]:top = mid_row + 1else:bottom = mid_row - 1return False