如何在O(n)时间内找出两个有序数组的所有匹配项（带比较次数限制）

问题背景 #

现有两个升序排列的数组：

• 数组A包含n个元素
• 数组B包含m个元素，且m < n
  需要找出两个数组中的所有匹配项，注意数组A中相邻元素可能对应数组B的同一元素。

约束条件 #

• 算法时间复杂度必须为O(n)
• 数组A中每个元素与B元素的比较次数最多为ceil(log(n))次（即每个A元素最多执行一次二分搜索）
• 元素比较只能用O(1)时间的compare函数，返回三种结果：两值匹配、前者小于后者、前者大于后者，无法直接合并数组。

此前尝试的方法及问题 #

• 逐元素遍历比较：如果A的所有元素都匹配B的最后一个元素，每个A元素都要和B的m个元素逐一比较，总比较次数达到n*m，直接超出单个元素最多ceil(log(n))次的限制。
• 分治+二分搜索：取A的中间元素在B中二分搜索，拆分B后递归处理A的前后两半。常规情况时间复杂度由T(n) = 2T(n/2) + logm推导，符合O(n)要求，但最坏情况（A所有元素对应B的最小/最大元素）下，每次递归都要处理整个B，时间复杂度退化为O(n logm)，不满足要求。

可行解决方案：双指针+动态范围二分搜索 #

核心思路是利用数组升序的特性，给B维护一个动态收缩的搜索范围，避免重复做无效的二分：

1. 初始化搜索范围：
   设low = 0（B当前搜索的起始索引），high = m-1（B当前搜索的结束索引），然后逐个遍历数组A的元素。

2. 对每个A元素做定向二分：
   在B的[low, high]范围内二分查找当前A元素a，根据compare的结果动态调整搜索范围：

   • 如果a小于B的中间元素：说明匹配项只能在左半部分，把high更新为中间索引-1，继续查找
   • 如果a大于B的中间元素：说明匹配项只能在右半部分，把low更新为中间索引+1，继续查找
   • 如果匹配成功：记录这个匹配项，同时因为A是升序的，后续元素不会比当前a小，所以保持low为当前匹配的索引（允许A相邻元素匹配同一个B元素），high不变。

3. 复杂度验证：

   • 每个A元素最多执行一次二分搜索，每次二分的比较次数是log(m)（因为m < n，log(m) ≤ ceil(log(n))），满足单个元素的比较次数限制。
   • 总时间复杂度：虽然单个二分是O(logm)，但low只会递增、high只会递减，整个遍历过程中二分的总比较次数是O(n + logm)，最终时间复杂度为O(n)，完全符合要求。

最坏情况验证 #

当A所有元素都等于B的最大元素时：
第一次二分找到B的最大元素后，low被设为该索引，后续A元素的二分搜索只会在[low, high]（也就是单个元素）范围内进行，每次只需要1次比较就能匹配，总比较次数是logm + (n-1)*1，属于O(n)级别，满足约束。

同理，当A所有元素等于B的最小元素时，第一次二分找到后high设为该索引，后续每次比较1次，总次数也是O(n)。

内容的提问来源于stack exchange，提问作者Julie Guo