## 【Leetcode】top 100 二分查找

news/2024/6/15 0:13:27/文章来源:https://blog.csdn.net/qq_45430996/article/details/137194242
###### 35 搜索插入位置

``````class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""left, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if target == nums[mid]:return midelif target < nums[mid]:right = mid-1else:left = mid+1return leftdef lower_bound(nums, target):left, right = 0, len(nums) - 1  # 闭区间 [left, right]while left <= right: mid = (left + right) // 2if nums[mid] < target:left = mid + 1         # 范围缩小到 [mid+1, right]else:right = mid - 1        # 范围缩小到 [left, mid-1]return left
``````
###### 74 搜索二维矩阵

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

或者将二维矩阵拉成一维矩阵然后同题35      时间复杂度相同O(logm+logn)

``class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""up, down = 0, len(matrix)-1while up <= down:mid = (up+down)//2if target == matrix[mid][0]: return Trueelif target < matrix[mid][0]:down = mid-1else:up = mid+1left, right = 0, len(matrix[0])-1while left <= right:mid = (left+right)//2if target == matrix[down][mid]: return Trueelif target < matrix[down][mid]:right = mid-1else:left = mid+1return False``

``class Solution:def searchMatrix(self, matrix, target):m, n = len(matrix), len(matrix[0])x, y = 0, n - 1while x < m and y >= 0:if matrix[x][y] > target:y -= 1elif matrix[x][y] < target:x += 1else:return Truereturn False``
###### 34 在排序数组中查找元素的第一个和最后一个位置

目标值没出现：nums[idx1] != target    （可以和idx1=0合并）

``class Solution(object):def searchRange(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""left, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if nums[mid] < target:left = mid+1else:right = mid-1idx1 = leftleft, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if nums[mid] < target+1:left = mid+1else:right = mid-1idx2 = left-1if idx1 == len(nums) or nums[idx1] != target: return [-1, -1]else: return [idx1, idx2]``
###### 33 搜索旋转排列数组

``class Solution(object):def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""left, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if nums[mid] == target: return midelif nums[left] == target: return leftelif nums[right] == target: return rightif nums[left] < nums[mid] :    # [left, mid]排序正确if nums[mid] > target and nums[left] < target:    # target在[left, mid]内  right = mid - 1else:left = mid + 1         elif nums[mid] < nums[right]:  # [mid, right]排序正确if nums[mid] < target and nums[right] > target:   # target在[mid, right]内  left = mid + 1else:right = mid - 1 else:return -1if not nums or nums[left] != target: return -1else: return left``
###### 153 寻找排序数组中的最小值

• 若旋转 `4` 次，则可以得到 `[4,5,6,7,0,1,2]`
• 若旋转 `7` 次，则可以得到 `[0,1,2,4,5,6,7]`

``class Solution(object):def findMin(self, nums):""":type nums: List[int]:rtype: int"""left, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if nums[left] < nums[mid] and nums[mid] < nums[right]:return nums[left]elif nums[left] < nums[mid] and nums[mid] > nums[right]:    # [left, mid]排序正确left = mid + 1      elif nums[left] > nums[mid] and nums[mid] < nums[right]:  # [mid, right]排序正确right = mid else:return min(nums[left], nums[right])``
###### 4 寻找两个正序数组的中位数

k=1，直接取两数组第一个元素的最小值；

``class Solution(object):def findMedianSortedArrays(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: float"""def getKthElement(k):index1, index2 = 0, 0while True:# 特殊情况if index1 == m:return nums2[index2 + k - 1]if index2 == n:return nums1[index1 + k - 1]if k == 1:return min(nums1[index1], nums2[index2])# 正常情况newIndex1 = min(index1 + k // 2 - 1, m - 1)        # 防止越界newIndex2 = min(index2 + k // 2 - 1, n - 1)pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]if pivot1 <= pivot2:k -= newIndex1 - index1 + 1index1 = newIndex1 + 1else:k -= newIndex2 - index2 + 1index2 = newIndex2 + 1m, n = len(nums1), len(nums2)totalLength = m + nif totalLength % 2 == 1:return getKthElement((totalLength + 1) // 2)else:return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2.``

### OmniGraffle Pro for mac 出色的图形设计软件

OmniGraffle Pro是一款非常出色的图形设计软件&#xff0c;它主要适用于Mac和iPad平台&#xff0c;可以用来轻松绘制各种精美的图表、示意图和界面设计。 软件下载&#xff1a;OmniGraffle Pro for mac中文注册激活版 以下是OmniGraffle Pro的一些主要特点和功能&#xff1a; 界…

### Java就近原则和this关键字

Java 中的就近原则和 this 关键字有着密切的关系&#xff0c;特别是在处理成员变量与方法参数同名的情况下。就近原则指的是在同一作用域下&#xff0c;优先使用最近声明的变量或参数。 在 Java 中&#xff0c;如果一个方法的参数与类的成员变量同名&#xff0c;为了明确指示要…

### HAL STM32 硬件I2C方式读取AS5600磁编码器获取角度例程

HAL STM32 硬件I2C方式读取AS5600磁编码器获取角度例程 &#x1f4cd;相关篇《STM32 软件I2C方式读取AS5600磁编码器获取角度例程》 ✨stm32使用硬件I2C去读取角度数据&#xff0c;通过STM32CubeMX工具配置工程&#xff0c;读取角度数据&#xff0c;只需要调用一个函数&#xf…