怎么选择兰州h5制作_现在做网站需要多少钱_晋城网站seo_网络营销环境宏观微观分析

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

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

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

二、35. 搜索插入位置

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

def binary_search(nums, target):left, right = -1, len(nums)while left+1 < right:  # 循环不变量# nums[left] <right# nums[right] >= rightmid  = (left+right) // 2if nums[mid] < target:  # 循环不变量对齐left = midelse:right = midreturn rightclass 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 = -1for i in range(m):if matrix[i][-1]==target:return Trueelif matrix[i][-1] > target:raw_tag = ibreakelse:passif raw_tag == -1:return Falsefor j in matrix[raw_tag]:if target == j:return Truereturn 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 * nwhile left + 1 < right:mid = (left + right) // 2x = matrix[mid // n][mid % n]if x == target:return Trueif x < target:left = midelse:right = midreturn False

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

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

def binary_search(nums, target):left, right = -1, len(nums)while left+1 < right:  # 循环不变量# nums[left] < target# nums[right] >= targetmid  = (left+right) // 2if nums[mid] < target:  # 循环不变量对齐left = midelse:right = midreturn 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) - 1return [start, end]