- LeetCode Hot 100 是最常被考察的题目集合，涵盖了面试中常见的算法和数据结构问题。
- 刷 Hot 100可以让你在有限的时间内集中精力解决最常考的问题。
- 不仅要写出代码，还要理解问题的本质、优化解法和复杂度分析。
- 遇到问题要多交流多求问多分享，“多折腾”能加深印象。
Day 3 二分查找专题训练
关注循环不变量，二分查找注意区间开闭。
更新发现前面做过的题会忘，所以可以4天一个周期。第4天做前面3天的题，补充笔记。
二分查找
35. 搜索插入位置
思路： 二分查找，采用左闭右闭区间，即是 left <= right均满足题意，更新mid需要偏移一个位置。
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1
while left <= right: # 使用左闭右闭区间，二分查找
mid = (left + right)//2 # //除法，向下取整
if nums[mid] < target:
left = mid + 1 # 更新时mid和left/right不会重叠，偏移（因为判断区间左闭右闭）
elif nums[mid] > target:
right = mid - 1
else:
return mid # 如果target在数组中，则返回位置
return left # target不在数组中，二分查找终止条件left > right, target应该插入right和left中间，因此为left/right+1
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
思路： 二分查找，给定的数组一般是①有序的，②不重复的。本题有重复，所以找的是左右边界。处理和传统的二分查找（上一题）不一样，在处理nums[mid]和target相等时，需要继续更新左右指针（根据要找的是左边界还是右边界）。
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def findLeftBar(nums, target): # 找到左边界，二分查找
leftBar = -1
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if nums[mid] >= target: # 如果出现相等，继续更新右指针，找到左边界
right = mid - 1
else:
left = mid + 1
if nums[mid] == target: # 记录下相等的坐标，最后一次循环，最后一次相等即为左边界
leftBar = mid
return leftBar
def findRightBar(nums, target): # 找到右边界，二分查找
rihgtBar = -1
left, right = 0, len(nums)-1
while left <= right: # 如果出现相等，继续更新左指针，找到右边界
mid = (left+right)//2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
if nums[mid] == target: # 记录下相等的坐标，最后一次循环，最后一次相等即为右边界
rihgtBar = mid
return rihgtBar
leftBar = findLeftBar(nums, target)
rihgtBar = findRightBar(nums, target)
return[leftBar, rihgtBar]
74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
思路： 之前的二分查找给定数组都是一维，二维数组也可以视作一维操作。只需确定在一维数组中索引为mid的元素在矩阵中对应的的位置。对于m*n的矩阵，对应的位置为matrix[mid//n][mid%n].
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
left, right = 0, m*n-1 # 二分查找，确定左右指针
while left <= right: # 左闭右闭区间
mid = (left+right)//2
x = matrix[mid//n][mid%n] # 根据mid的值，判断其在矩阵中位置
if x > target:
right = mid - 1 # 左闭右闭区间对应偏移
elif x < target:
left = mid + 1
else:
return True
return False
33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
思路：
- 通过比较 nums[left] 和 nums[mid]，我们判断 mid 所在的子数组（左有序组还是右有序组）。
- 根据 target 与 nums[mid] 的关系，决定下一步在左半部分还是右半部分继续查找。
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums)-1
while left <= right:
mid = (left + right)//2
if nums[mid] == target: return mid
# 判断 mid 是在左半部分还是右半部分
if nums[left] <= nums[mid]: # 左半部分有序
if nums[left] <= target < nums[mid]: # 在左半部分则更新mid
right = mid - 1
else:
left = mid + 1
else: # 右半部分有序
if nums[mid] < target <= nums[right]: # 在右半部分则更新mid
left = mid + 1
else:
right = mid - 1
return -1
153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
- 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
**思路：**最小值出现在右侧有序组的最左边，因此比较mid和nums[-1]可以二分法缩小区间。nums[mid] <= nums[-1]判断mid是在左部分还是右部分。
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums)-1
while left <= right: # 二分查找，左闭右闭区间
mid = (left + right)//2
if nums[mid] <= nums[-1]: # mid在右有序区间，最小值在mid不在其右侧；等号必须取
right = mid - 1 # left = right时找到最小值，left是对应的索引
else:
left = mid + 1
return nums[left]
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
思路：
给定两个有序数组找中位数，当作一个有序序列处理，需要有两个指针分别遍历两数组，遍历len(m+n)//2+1次得到结果。
核心在于：如何判断移动哪个数组对应的指针。
很容易想到比较两指针对应的元素大小，移动小的。
- 这里也要考虑到较短的数组遍历完的情况。
写出一个m_start指针移动：前提m_start < len(nums)，满足nums1(m_start) < nums2[b] 或者 n_start ≥ len(nums2).
这里有个小坑，在于后面条件的顺序不能反，如果写反了，就会报IndexError.
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m = len(nums1)
n = len(nums2)
length = m + n # 判断两个数组一共有多少个数
pre = now = 0 # now记录当前遍历到的值，pre记录上一个遍历到的值
m_start = n_start = 0 # 使用以长度为标识的指针，分别遍历两数组
for i in range(length//2+1): # 无论总长度是奇数还是偶数，都需遍历(长度//2)+1次
pre = now # 每次遍历需更新pre
# nums1的指针不超过nums1长度且 ①其值比nums2指针元素小/ ② nums2已遍历完
if m_start < m and (n_start >= n or nums1[m_start] < nums2[n_start]):
now = nums1[m_start] # 记录下当前遍历的元素
m_start += 1 # 移动指针
else:
now = nums2[n_start]
n_start += 1
if length % 2 == 1: # 如果总长度为奇数，最后一个遍历的数为中位数
return now
else:
return (pre + now)/2 # 如果总长度为偶数，取其和前一个遍历数的均值
![RT-DETR融合[CVPR2023]FFTformer中的FSAS模块](https://i-blog.csdnimg.cn/direct/63687d37642843b29d6bdaa06a7796ac.png)
