连续二分搜索在有序数组匹配中的时间复杂度分析

问题概述 #

给定两个有序数组A（含n个元素）和B（含m个元素），需找出两者的所有匹配元素。采用了一种类无限数组的连续二分搜索算法：对B中每个元素，以上次匹配结果的位置为起始点，先检查A中prevResultIndex + 2^k位置的元素，找到首个大于等于目标值的位置后，在prevResultIndex + 2^(k-1)到prevResultIndex + 2^k区间内执行二分搜索，将结果作为下次搜索的起始点。

算法限制B中每个元素与A的比较次数不超过ceil(logn)，未使用合并或遍历的常规方法。现需明确两个问题：

1. 该算法的时间复杂度能否证明为O(n)？
2. 该算法是否确实优于O(nlogn)？

算法示例 #

以索引从1开始的数组为例：

• A = [1,2,3,4,5,6,7,8,9,10,11]，B = [3,9]
• 步骤1：处理B[1]，检查A[1]、A[2]、A[4]，确定目标在A[2..4]区间，执行二分搜索；
• 步骤2：处理B[2]，从上次结果位置（3）开始，依次检查A[3]（3+2^{0）、A[4]（3+2}1）、A[7]（3+2^{2）、A[11]（3+2}3），确定目标在A[7..11]区间，执行二分搜索。

实现代码 #

def continuousBinary(A, n, B, m):
    i = 1
    prevResultIndex = 0
    while i < m:
        k = 0
        while A[prevResultIndex + pow(2,k)] < B[i]:
            k+=1
        prevResultIndex = binarySearch(B[i], A, prevResultIndex + pow(2,k-1), prevResultIndex + pow(2,k))

解答 #

1. 时间复杂度分析 #

首先明确：该算法的时间复杂度并非严格O(n)，需分情况讨论：

前提假设

该算法的优化逻辑成立的核心前提是数组B也是非递减有序的——否则prevResultIndex无法保证单调递增，后续搜索可能回退到A的前面位置，导致重复访问，复杂度会退化为O(m log n)。

最优情况：O(m + n)

当B有序时，prevResultIndex每次搜索后单调递增，此时：

• 指数跳跃阶段：A中的每个位置最多被访问一次（后续搜索的起始点都在之前的结果位置之后），所有跳跃操作的总比较次数为O(n)。
• 二分搜索阶段：如果B中的元素在A中分布密集（比如B是A的连续子集），每次二分搜索的区间很小，累计比较次数为O(m)。
  两者相加，总时间复杂度为O(m + n)，即线性复杂度。

最坏情况：O(m log n)

如果B中的元素在A中分布极其稀疏（比如每个B元素对应A末尾附近的元素），那么每个元素的指数跳跃和二分搜索都需要O(log n)次比较，总复杂度为O(m log n)，和逐个元素单独二分搜索的复杂度一致。

2. 是否优于O(nlogn)？ #

需结合具体场景对比：

• 若对比“对B中每个元素单独做二分搜索”的O(m log n)算法：
  当B有序时，该算法在多数实际场景下性能更优——利用之前的搜索结果，避免重复扫描A的前缀部分，累计比较次数更少。但最坏情况下两者复杂度相同。
• 若对比O(n log n)级别的算法（比如对无序数组A排序后处理，或其他低效的交集算法）：
  当m远小于n时，O(m log n)的复杂度显然优于O(n log n)；当m与n接近时，该算法的最优线性复杂度O(m + n)远优于O(n log n)，最坏情况O(m log n)也和O(n log n)相当（m≈n时）。

不过要注意，常规的双指针法找两个有序数组的交集，时间复杂度是严格O(n + m)，且实现更简单，最坏情况比该算法更稳定。但该算法的优势在于无需额外空间，且当B元素数量较少时，搜索效率可能高于双指针法（无需遍历整个A）。

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