旋转数组搜索、寻找第K小元素、二分答案法——二分不只是查找
第4课我们学了基础的二分查找——在有序数组中找目标值。但二分的思想远不止于此！二分的本质是在一个具有单调性的答案空间上高效搜索。"单调性"不一定指数组有序，而是指"如果某个答案不满足，那么更差的答案也不满足"。
题目描述：给定一个升序排列的整数数组 nums，在某个点旋转后（例如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]），搜索目标值 target，返回其索引，不存在则返回 -1。
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
# 判断哪半有序
if nums[left] <= nums[mid]: # 左半有序
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # 右半有序
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1时间复杂度：O(log n)，空间复杂度：O(1)
nums[left] <= nums[mid] 用了 ≤ 而不是 <，因为当 left == mid 时（只剩2个元素），左半只有一个元素也算"有序"。如果改为 <，当 left == mid 时会进入 else 分支，逻辑虽然也对但不够直观。题目描述：给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2，找出并返回这两个正序数组的中位数。要求时间复杂度 O(log(m+n))。
i，则另一个数组的分割点 j = (m+n+1)//2 - i。检查分割是否合法：nums1[i-1] ≤ nums2[j] 且 nums2[j-1] ≤ nums1[i]。如果 nums1[i-1] > nums2[j]，说明 i 太大，右移；如果 nums2[j-1] > nums1[i]，说明 i 太小，左移。
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 确保在较短数组上二分
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total_left = (m + n + 1) // 2
left, right = 0, m
max_left = 0
while left <= right:
i = (left + right) // 2
j = total_left - i
nums1_left = float('-inf') if i == 0 else nums1[i-1]
nums1_right = float('inf') if i == m else nums1[i]
nums2_left = float('-inf') if j == 0 else nums2[j-1]
nums2_right = float('inf') if j == n else nums2[j]
if nums1_left <= nums2_right and nums2_left <= nums1_right:
# 找到合法分割
max_left = max(nums1_left, nums2_left)
if (m + n) % 2 == 1:
return max_left
min_right = min(nums1_right, nums2_right)
return (max_left + min_right) / 2.0
elif nums1_left > nums2_right:
right = i - 1
else:
left = i + 1
return 0.0时间复杂度：O(log(min(m,n)))，空间复杂度：O(1)
(m+n+1)//2 保证奇数时左半多一个元素。题目描述：珂珂每小时选择一堆香蕉，吃掉 k 根（不够则吃完这堆），在 h 小时内吃完所有香蕉。求最小的 k。
sum(ceil(pile/k))，判断是否 ≤ h。
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
left, right = 1, max(piles)
result = right
while left <= right:
mid = (left + right) // 2
hours = sum((p + mid - 1) // mid for p in piles)
if hours <= h: # 能吃完，尝试更小的k
result = mid
right = mid - 1
else: # 吃不完，需要更大的k
left = mid + 1
return result时间复杂度：O(n × log(max(piles)))，空间复杂度：O(1)
# 二分答案法通用模板
def binary_search_answer(nums, condition):
"""
condition(x) 返回True表示x可行
求: 最大的不可行 → 最小的可行 (或反过来)
"""
left, right = min_answer, max_answer
result = right # 默认最大值
while left <= right:
mid = (left + right) // 2
if condition(mid): # mid可行, 尝试更优
result = mid
right = mid - 1 # 求最小可行值
# left = mid + 1 # 求最大可行值
else: # mid不可行
left = mid + 1 # 需要更大
# right = mid - 1 # 需要更小
return result
# 常见变体:
# 1. 求最小可行值: 能行就右移right
# 2. 求最大可行值: 能行就左移left
# 3. 浮点二分: 用eps控制精度, 循环100次或 |right-left|与 LC 33 互补的问题——不找 target，而是找最小值。
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[right]:
# mid在旋转点左侧 → 最小值在右边
left = mid + 1
else:
# mid在旋转点右侧(或就是最小值) → 最小值在左边
right = mid
return nums[left]nums[mid] > nums[right] 说明 mid 在旋转点的左侧（左半较大的部分），最小值在右侧，left = mid + 1。否则最小值在 mid 或左侧，right = mid。最终 left == right 就是最小值的位置。
nums[left] ≤ nums[mid] → 左半有序nums[mid] > nums[right] 判断