二分查找[64-69]

時間復雜度O(log n)，要想到二分排序

35.搜索插入位置

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:left = 0right = len(nums)-1while left <= right:  #左閉右閉mid = (left+right)//2if nums[mid] < target:left = mid + 1elif nums[mid] > target:right = mid -1else: return midreturn 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 = 0right = m*n -1while left <= right:mid = (left+right)//2i = mid // nj = mid % nif matrix[i][j] < target:left = mid + 1elif matrix[i][j] > target:right = mid - 1else:return Truereturn False

34.在排序數組中查找元素的第一個和最后一個位置

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if len(nums) == 0: return [-1,-1]left = 0right = len(nums)-1while left <= right:mid = (left+right)//2if nums[mid] < target:left = mid +1elif nums[mid] > target:right = mid-1else :i = j = midwhile i>=0 and nums[i] == target:i -= 1while j<len(nums) and nums[j] == target:j += 1return [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)-1while left<=right: # 不變量：左閉右閉區間middle = left + (right-left) //2 if nums[middle] >= target: right = middle - 1else: left = middle + 1return 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 = 0right = len(nums)-1while left<= right:mid = (left+right)//2   #mid要么左邊升序，要么右邊升序if nums[mid] == target: return midelif nums[mid] < nums[right]:   #[mid,right]右邊升序if target > nums[mid] and target <= nums[right]: #target在區間（mid,right]left = mid +1else: right = mid-1else:   #[left, mid],左邊升序if target >= nums[left] and target < nums[mid]: #target在區間[left, mid）right = mid -1else: left = mid +1 return -1

153.尋找旋轉排序數組中的最小值

4.尋找兩個正序數組的中位數

棧

堆