核心：二分查找高级应用——峰值搜索与旋转排序数组，利用红蓝染色法和分类讨论解决复杂二分问题，将边界判断转化为颜色划分。
一、基础知识点（峰值与旋转排序数组）
1. 寻找旋转排序数组的峰值
问题定义
给定数组，找到一个峰值（严格大于左右相邻元素的元素）。可能有多个峰值。
核心思路
红蓝染色法：将数组元素染成红色（峰值左侧）或蓝色（峰值或峰值右侧）
由于峰值一定存在，数组最右侧元素一定是蓝色
在区间 [0, N-2] 内二分，比较 mid 与 mid+1 的大小来染色
染色规则
nums[mid] < nums[mid+1]：mid 在峰值左侧，mid 及左侧染红色nums[mid] > nums[mid+1]：mid 是峰值或在其右侧，mid 及右侧染蓝色
复杂度
时间：O(logn) 空间：O(1)
Python 实现
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
n = len(nums)
# 开区间 left=-1, right=n-1，对应闭区间 [0, n-2]
left = -1
right = n - 1
while left + 1 < right: # 开区间不为空
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
# mid 在峰值左侧，染红色，left 收缩到 mid
left = mid
else:
# mid 是峰值或在其右侧，染蓝色，right 收缩到 mid
right = mid
return right
2. 寻找旋转排序数组的最小值
问题定义
给定可能旋转的升序数组（原数组升序，旋转后分为两段），找到数组中的最小元素。
核心思路
利用最后一个元素作为比较基准（最小值一定在数组中）
在区间 [0, N-2] 内二分，判断 mid 在最小值左侧还是右侧
判定规则
nums[mid] < nums[n-1]：mid 是最小值或在最小值右侧 → 蓝色nums[mid] > nums[n-1]：mid 在最小值左侧 → 红色
复杂度
时间：O(logn) 空间：O(1)
Python 实现
class Solution:
def findMin(self, nums: List[int]) -> int:
n = len(nums)
left = -1 # 红色边界
right = n - 1 # 蓝色边界（数组最后一个元素一定是蓝色）
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] < nums[n - 1]:
# mid 在最小值右侧或就是最小值，染蓝色
right = mid
else:
# mid 在最小值左侧，染红色
left = mid
return nums[right]
3. 搜索旋转排序数组中的目标值
问题定义
给定可能旋转的升序数组和一个 target，在数组中查找 target 是否存在。
核心思路
一次二分解决，分四种情况讨论：
设 end = nums[n-1]，判断 mid 在哪一段，以及 mid 与 target 的大小关系。
蓝色判定（target 在 mid 左侧或 mid 就是目标）
nums[mid] > end（左段）且target <= end（target 在左段）且nums[mid] >= targetnums[mid] > end（左段）且target > end（target 在右段）nums[mid] <= end（右段）且nums[mid] >= target
复杂度
时间：O(logn) 空间：O(1)
Python 实现
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
# 判断 mid 在哪一段
if nums[mid] > nums[n - 1]: # 左段
if target > nums[n - 1] and nums[mid] > target:
right = mid - 1
else:
left = mid + 1
else: # 右段
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
二、练习（3道经典二分题目）
1. 搜索二维矩阵 🔢
题目描述（LeetCode 74 - 中等）
给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列
每行的第一个整数大于前一行的最后一个整数
给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。
示例
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
解题思路
从矩阵右上角开始搜索（左下角也可）
当前位置值等于 target → 找到
当前位置值小于 target → 下移（行增大）
当前位置值大于 target → 左移（列减小）
复杂度
时间：O(m + n)
空间：O(1)
Python 代码
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
i, j = 0, n - 1 # 从右上角开始
while i < m and j >= 0:
if matrix[i][j] == target:
return True
if matrix[i][j] < target:
i += 1 # 下移
else:
j -= 1 # 左移
return False
2. 寻找峰值 II 🎯
题目描述（LeetCode 1901 - 中等）
一个 2D 网格中的峰值是指那些严格大于其相邻格子（上、下、左、右）的元素。给你一个从 0 开始编号的 m x n 矩阵 mat，其中任意两个相邻格子的值都不相同。找出任意一个峰值 mat[i][j] 并返回其位置 [i,j]。你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法。
示例
输入: mat = [[1,4],[3,2]]
输出: [0,1]
解释: 3 和 4 都是峰值，所以 [1,0] 和[0,1]都是可接受的答案。
解题思路
二维二分：先在行上二分，找到当前行最大值
比较最大值与下一行对应列的值：
max(mat[i]) > mat[i+1][col]→ 峰值在当前行或上方否则 → 峰值在当前行下方
复杂度
时间：O(m log(n)) 或 O(n log(m))
空间：O(1)
Python 代码
class Solution:
def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
left, right = 0, len(mat) - 2
while left <= right:
i = (left + right) // 2
# 找到当前行最大值及其列索引
mx = max(mat[i])
col = mat[i].index(mx)
if mx > mat[i + 1][col]:
# 峰值在当前行或上方
right = i - 1
else:
# 峰值在当前行下方
left = i + 1
return [left, mat[left].index(max(mat[left]))]
3. 寻找旋转排序数组中的最小值 II 🧩
题目描述（LeetCode 154 - 困难）
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]]。
给你一个可能存在重复元素值的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
示例
输入：nums = [1,3,5]
输出：1
解题思路
与 154 题类似，但数组可能包含重复元素
使用红蓝染色法，在 [0, n-2] 区间二分
当
nums[mid] == nums[right]时，右指针左移一位（应对重复元素）
复杂度
时间：最坏 O(n)，平均 O(logn)
空间：O(1)
Python 代码
class Solution:
def findMin(self, nums: List[int]) -> int:
n = len(nums)
left = -1
right = n - 1
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] == nums[right]:
# 重复元素，右指针左移缩小范围
right -= 1
elif nums[mid] > nums[right]:
# mid 在最小值左侧，染红色
left = mid
else:
# mid 在最小值右侧，染蓝色
right = mid
return nums[right]
三、二分查找高级技巧总结 ✨
红蓝染色法
将数组元素染成红色（答案左侧）或蓝色（答案或右侧），通过二分不断收缩边界。
适用场景
峰值搜索
旋转排序数组最小值
答案在数组中且有明确边界
关键点
确定蓝色边界（一定是答案或答案右侧）
在开区间 [left, right) 上二分，初始化 left = -1, right = n（或 n-1）
循环结束时，
left + 1 == right，right 即为答案
旋转排序数组解题策略
分类方法
根据 nums[mid] 与 nums[n-1] 的关系判断 mid 在哪一段（左段 / 右段）
一次二分法
通过详细分类讨论，将两段分别查找的逻辑合并为一次二分
复杂度速记
基础二分：O(logn)
旋转排序数组：O(logn)
二维矩阵搜索：O(m+n)
二维峰值搜索：O(m logn) 或 O(n logm)