如何以O(logn)复杂度判断有序子数组是否包含于大有序数组

核心思路 #

利用两个数组的有序性，通过二分查找快速定位关键位置，再通过分治式的二分验证确保子数组完全匹配，整体时间复杂度控制在O(logn)。

具体步骤 #

1. 边界校验

   • 若子数组v'为空（k=0），直接返回TRUE；
   • 若k > n，直接返回FALSE（子数组长度超过原数组，不可能包含）。

2. 定位子数组尾元素在原数组中的位置

   • 使用二分查找在v中找到v'[k-1]的任意一个匹配索引last_pos（若不存在，直接返回FALSE）；
   • 计算候选起始位置：start_candidate = last_pos - k + 1。若start_candidate < 0，返回FALSE（起始位置越界）。

3. 验证候选区间的匹配性

   • 首先检查v[start_candidate]是否等于v'[0]，若不等，返回FALSE；
   • 采用分治式二分验证：迭代地检查v'的中间元素是否与v中对应位置（start_candidate + mid）的元素相等：
     • 取v'的当前范围中间索引mid = (left + right) // 2，若v[start_candidate + mid] != v'[mid]，返回FALSE；
     • 若左半部分（left到mid-1）长度大于0，继续验证左半部分；
     • 若右半部分（mid+1到right）长度大于0，继续验证右半部分；
   • 所有元素验证通过后，返回TRUE。

示例验证 #

以题目给出的例子：

• v = [-10,-3,0,4,7,19,33]，n=7；v' = [4,7,19]，k=3

1. 边界校验：k=3<=7，正常；
2. 查找v'[2]=19在v中的位置是5，start_candidate=5-3+1=3；
3. 检查v[3]=4等于v'[0]=4；
4. 验证中间元素：mid=(0+2)//2=1，v[3+1]=7等于v'[1]=7；左半部分（0到0）和右半部分（2到2）无需再拆分验证，所有元素匹配，返回TRUE。

复杂度分析 #

• 二分查找定位尾元素：O(logn)；
• 分治式验证：每次将验证范围减半，时间复杂度为O(logk)，由于k<=n，故O(logk) <= O(logn)；
• 整体时间复杂度：O(logn) + O(logk) = O(logn)，符合要求。

内容的提问来源于stack exchange，提问作者j.j.3