什么问题适合二分查找

1. 序列数据单调有序（可能是问题已有序列，也可能是答案构建的序列）
2. 目标值唯一或存在边界（在某范围内查找满足阈值的最值等）

二分查找的框架

经典有序数组查找

找到等于目标值的位置

while left < right:
	mid = (left + right) >> 1
	if nums[mid] < target:
		left = mid + 1
	elif nums[mid] > target:
		right = mid - 1
	else:
		# 满足条件
		return mid
return -1

查找第一个大于等于目标值的位置

while left < right:
	mid = (left + right) >> 1
	if nums[mid] < target:
		left = mid + 1
	else:
		right = mid
		# 注意！满足条件情况下，继续保留mid作为候选项
return left # 或 right，此时 left == right

变形包括：大于、小于、小于等于
核心在于满足条件时 mid 继续被保留为候选项，在此基础上，什么判断代表条件满足、满足后是剔除左半还是右半等等问题都要根据实际情况来写

二分答案

什么问题适合二分答案

1. 要求最优值，并且这个值存在于一个有序连续区间内
2. 直接求解困难，但验证某值是否可行是容易的
3. 可行性有单调性，判断条件时看 mid 是取大了还是小了，能直接推出应该缩 left 还是 right

常见情况：最小值最大化、最大值最小化（因为这类优化问题往往直接求解困难，而可行性判断通常可以用贪心或简单方法实现，且可行性随 SS 单调变化，非常适合二分答案）

代码模板

1. 找最小值，也就是找左边界

while left < right:
	mid = (left + right) >> 1
	if check(mid):
		right = mid
		# 找最小值，而此时是满足条件的，那么就应该缩上界。且mid还应保留作为候选
	else:
		left = mid + 1
return left # 或 right，此时 left == right

2. 找最大值，也就是找右边界
   当 left = mid 时，使用 mid = (left + right + 1) >> 1
   因为当 left 和 right 相邻，mid = (left + right) // 2 向下取整会导致 mid 始终等于 left，陷入死循环！

while left < right:
	mid = (left + right + 1) >> 1
	# 注意！当left与right相邻时，此处通过+1强制mid指向了right
	if check(mid):
		left = mid
		# 找最大值，而此时是满足条件的，那么就应该缩下界。且mid还应保留作为候选
	else:
		right = mid - 1
return left # 或 right，此时 left == right

二维矩阵中的二分

二维矩阵行内和列内均有序

采用对角线遍历，也叫斜向层序遍历

二维矩阵行内和列内有序+行间有序

直接展平为一维数组，一维坐标 idx 对应的二维坐标为 row = idx // n; col = idx % n;

第 k 大/小

理解

二分查找的精髓就是快速向正确方向找值
二分答案的精髓就是自己创建候选项+判断约束条件+快速向正确方向找值
第 k 大/小的精髓就是自己创建候选项+快速判断是否满足第 k 大/小的约束条件+快速向正确方向找值
以上快速均指的是二分 nlpg 快速查找

典型例题及解法

由于数据结构的维度差异，例举两种典型情况：两个一维有序数组和一个二维有序矩阵

两个一维有序数组

题目：
给定两个独立的有序数组，从中找到所有数中第 k 小的数

解法：
二分排除法和二分答案法都可以，只是二分排除法更快 O(log(min(m, n))) ，二分答案法需要值域范围，更慢 O(log(f_range)*log(m+n))，所以优先二分排除法，参照以下过程。
比较两个数组的第 k/2 个元素。假设两个数组分别为 A 和 B，起始下标为 startA 和 startB。令 p = k // 2（向下取整）。比较 A[startA + p - 1] 和 B[startB + p - 1]：

• 如果 A[startA + p - 1] <= B[startB + p - 1]，则 A 的前 p 个元素一定属于最小的 k 个元素中的一部分，可以排除它们，然后递归地在剩下的数组中找第 k-p 小的元素。
• 否则，排除 B 的前 p 个元素。
  递归终止条件：
• 如果某个数组的起始下标超出数组长度，即该数组全部被排除了，则直接返回另一个数组的第 k （每次迭代会更新 k = k-p）个元素。
• 如果 k == 1，返回两个数组当前起始位置的最小值。

一个二维有序矩阵

题目：
给定一个 n×n 的有序矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

解法：
二分排除法不适用，因为无法简单地通过比较某一行/列的第 k/2 个元素来排除一块区域，矩阵的“行”和“列”不是两个独立的序列，排除一块区域后剩余部分不再是完整的矩形，难以递归。因此，仅用二分答案法，参照以下过程。
假设矩阵为 m， 则值域为 [m[0][0], m[n-1][n-1]]，left = matrix[0][0], right = matrix[n-1][n-1]，目标是找到最小的值 mid ，使得当整个矩阵中小于等于 mid 值的元素个数大于等于 k

• 定义计数函数count(mid) 返回矩阵中 ≤ mid 的元素个数。利用矩阵每行有序，对每一行用二分查找（或 bisect_right）累加。