Hot100刷题计划-Day3 二分查找专题【持续更新】

• 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 - 1else: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 = -1left, right = 0, len(nums)-1while left <= right:mid = (left+right)//2if nums[mid] >= target:  # 如果出现相等，继续更新右指针，找到左边界right = mid - 1else:left = mid + 1if nums[mid] == target:  # 记录下相等的坐标，最后一次循环，最后一次相等即为左边界leftBar = midreturn leftBardef findRightBar(nums, target): # 找到右边界，二分查找rihgtBar = -1left, right = 0, len(nums)-1while left <= right:       # 如果出现相等，继续更新左指针，找到右边界mid = (left+right)//2if nums[mid] <= target:left = mid + 1else:right = mid - 1if nums[mid] == target:  # 记录下相等的坐标，最后一次循环，最后一次相等即为右边界rihgtBar = midreturn rihgtBarleftBar = 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)//2x = matrix[mid//n][mid%n] # 根据mid的值，判断其在矩阵中位置if x > target:right = mid - 1      # 左闭右闭区间对应偏移elif x < target:left = mid + 1else:return Truereturn 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)-1while left <= right:mid = (left + right)//2if nums[mid] == target: return mid# 判断 mid 是在左半部分还是右半部分if nums[left] <= nums[mid]:   # 左半部分有序if nums[left] <= target < nums[mid]: # 在左半部分则更新midright = mid - 1else:left = mid + 1else: # 右半部分有序if nums[mid] < target <= nums[right]: # 在右半部分则更新midleft = mid + 1else:right = mid - 1return -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)-1while left <= right:  # 二分查找，左闭右闭区间mid = (left + right)//2if nums[mid] <= nums[-1]:  # mid在右有序区间，最小值在mid不在其右侧；等号必须取right = mid - 1       # left = right时找到最小值，left是对应的索引else:left = mid + 1return 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 += 1if length % 2 == 1:          # 如果总长度为奇数，最后一个遍历的数为中位数 return nowelse:return (pre + now)/2     # 如果总长度为偶数，取其和前一个遍历数的均值