第三讲 Binary Search

二分查找（Binary Search）

元素查找（Element Search）

一个序列\(A\)满足\(A_1>A_n\)，找到任意一个下标\(i\)，使得\(A_i>A_{i+1}\)。考虑二分

若\(A_{mid}>A_{mid+1}\)，返回\(mid\)，否则
若\(A_{mid}\geqslant A_1\)，考虑区间\([mid+1,R]\)；
若\(A_{mid}<A_1\)，考虑区间\([1,mid-1]\)

时间复杂度为\(O(\log n)\)

循环不变量：对于区间\([L,R]\)，总有\(A_L>A_R\)

中位数查找（Median Sreach）（期中不考）

输入两个递增排序的数列\(A[1,\cdots,n],B[1,\cdots,n]\)，求\(A\cup B\)的中位数

假设中位数在\(A\)中，且当前讨论区间记为\([L,R]\)求出\(A_{mid}\)在\(B\)中的排名\(r\)（第\(r\)小，即\(B\)中第一个大于\(A_{mid}\)的元素下标）
若\((mid-1)+(r-1)<n-1\)，则考虑区间\([mid+1,R]\)；否则考虑\([L,mid]\)

假设最终得到的结果为\(A_p\)，还需进行检验，求出其在\(B\)中的排名\(r'\)，若\(p+r'=n-1\)，则\(A_p\)为中位数，否则需要交换\(A,B\)，在\(B\)中做一次对称查找。

总时间复杂度为\(O(\log^2 n)\)

优化方向一：比较部分简化为：\(A[mid]<B[n-mid+1]\)，时间复杂度降为\(O(1)\)；

优化方向二：当\(A_{n/2}<B_{n/2}\)时，中位数不可能在\(A[1,\cdots,n/2],B[n/2+1,\cdots,n]\)中。

比较\(A[n/2],B[n/2]\)
若\(A_{n/2}\leqslant B_{n/2}\)，对\(A[n/2+1,\cdots,n],B[1,\cdots,n/2]\)递归操作
若\(A_{n/2}>B_{n/2}\)，对\(A[1,\cdots,n/2],B[n/2+1,\cdots,n]\)递归操作

当\(A,B\)递归区间长度均为1时，较小的为中位数。

时间复杂度为\(O(\log n)\)

一维峰值查找（1D Peak Finding）

输出一个序列的任意一个局部最大值（输入序列保证存在局部最大值）（注意，若\(A_1>A_2\)，则\(A_1\)是峰值，若\(A_n>A_{n-1}\)，则\(A_n\)是峰值。）

对\([L,R]\)：

若\(mid\)不在左端点且\(A_{mid-1}>A_{mid}\)，则\(R\gets mid-1\);

若\(mid\)不在右端点且\(A_{mid+1}>A_{mid}\)，则\(L\gets mid+1\)；

否则，返回\(A_{mid}\)

思考：这个算法流程为什么是正确的？

二维峰值查找（2D Peak Finding）

输出二维数阵的任意一个局部最大值（输入序列保证存在局部最大值）

方法一：用每一列的最大值代替这一列，压缩得到一行，对这一行使用1D Peak Finding算法，得到的行峰值即为数阵局部最大值。

时间复杂度为\(O(n^2)+O(\log n)=O(n^2)\)

方法二：设当前处理的是第\(L\sim R\)列，取\(mid=(L+R)/2\)，查找第\(mid\)列中的最大值\(A_{mid,j}\)，\(A_{mid,j}\)若是峰值，返回\(A_{mid,j}\)即可，否则，若\(A_{mid,j}<A_{mid+1,j}\)，则\(L=mid+1\)，若\(A_{mid,j}<A_{mid-1,j}\)，则\(R=mid-1\)。

正确性说明：假设下一步处理第\(mid+1\sim R\)列，记此区域为\(H\)。设 \((r, c)\) 是整个区域 \(H\) 中的全局最大值所在的位置。我们从 \(A_{mid, j} < A_{mid+1, j}\) 触发向右搜索\(A_{r, c} \ge A_{mid+1, j} > A_{mid, j} \ge A_{mid, r}\) \(\implies\) \(A_{r, c} > A_{mid, r}\)。这证明了：右半部分的全局最大值一定严格大于它在左边界外的邻居。

时间复杂度满足\(T(n)=T(n/2)+O(n)=O(n\log n)\)

方法三：按田字划分数阵，在中间围成四个子数阵，查找田字划分线上的最大值\(A_{i,j}\)，将其与相邻的数进行比较，如果有比它更大的元素，那么这个元素一定位于某个子数阵中，可以证明：这个子数阵内部的最大值，一定是整个原始大数阵的一个峰值。

时间复杂度\(T(n,n)\leqslant T(n/2,n/2)+4n=O(n)\)