二分查找[64-69]
时间复杂度O(log n)，要想到二分排序
35.搜索插入位置
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
while left <= right: #左闭右闭
mid = (left+right)//2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid -1
else:
return mid
return mid+1 if nums[mid] < target else mid
74.搜索二维矩阵
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix) #行
n = len(matrix[0]) #列
left = 0
right = m*n -1
while left <= right:
mid = (left+right)//2
i = mid // n
j = mid % n
if matrix[i][j] < target:
left = mid + 1
elif matrix[i][j] > target:
right = mid - 1
else:
return True
return False
34.在排序数组中查找元素的第一个和最后一个位置
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if len(nums) == 0:
return [-1,-1]
left = 0
right = len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] < target:
left = mid +1
elif nums[mid] > target:
right = mid-1
else :
i = j = mid
while i>=0 and nums[i] == target:
i -= 1
while j<len(nums) and nums[j] == target:
j += 1
return [i+1, j-1]
return [-1,-1]
# 1、首先，在 nums 数组中二分查找得到第一个大于等于 target的下标leftBorder；
# 2、在 nums 数组中二分查找得到第一个大于等于 target+1的下标， 减1则得到rightBorder；
# 3、如果开始位置在数组的右边或者不存在target，则返回[-1, -1] 。否则返回[leftBorder, rightBorder]
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(nums:List[int], target:int) -> int:
left, right = 0, len(nums)-1
while left<=right: # 不变量：左闭右闭区间
middle = left + (right-left) //2
if nums[middle] >= target:
right = middle - 1
else:
left = middle + 1
return left # 若存在target，则返回第一个等于target的值
leftBorder = binarySearch(nums, target) # 搜索左边界
rightBorder = binarySearch(nums, target+1) -1 # 搜索右边界
if leftBorder == len(nums) or nums[leftBorder]!= target: # 情况一和情况二
return [-1, -1]
return [leftBorder, rightBorder]
33.搜索旋转排序数组
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
while left<= right:
mid = (left+right)//2 #mid要么左边升序，要么右边升序
if nums[mid] == target:
return mid
elif nums[mid] < nums[right]: #[mid,right]右边升序
if target > nums[mid] and target <= nums[right]: #target在区间（mid,right]
left = mid +1
else:
right = mid-1
else: #[left, mid],左边升序
if target >= nums[left] and target < nums[mid]: #target在区间[left, mid）
right = mid -1
else:
left = mid +1
return -1
153.寻找旋转排序数组中的最小值
