本文介绍了一种在 O(max(log n, k)) 时间复杂度内，判断一个大小为 k 的已排序子数组是否存在于一个大小为 n 的已排序数组中的方法。该方法基于二分查找定位子数组的起始元素，并进行后续验证，尤其适用于 n 远大于 k 的情况。
问题描述
给定两个已排序的数组 v (大小为 n) 和 v' (大小为 k，其中 k <= n)，目标是确定 v' 是否作为连续子数组存在于 v 中。例如，v = [-10, -3, 0, 4, 7, 19, 33] 和 v' = [4, 7, 19]，则应该返回 True。
解决方案
该问题的核心在于利用已排序数组的特性，结合二分查找和线性验证，将时间复杂度控制在 O(max(log n, k))。
算法步骤
二分查找起始元素： 在较大的数组 v 中，使用二分查找算法查找子数组 v' 的第一个元素。二分查找的时间复杂度为 O(log n)。
线性验证： 如果在 v 中找到了 v' 的第一个元素，则从该位置开始，线性地比较 v 和 v' 的剩余元素。需要注意的是，这里假设 v' 中的元素必须在 v 中连续存在。线性验证的时间复杂度为 O(k)。
Python 代码示例
def is_subarray_present(v, v_prime):
"""
检查排序子数组 v_prime 是否存在于更大的排序数组 v 中。
Args:
v: 大的排序数组。
v_prime: 需要检查的排序子数组。
Returns:
如果 v_prime 存在于 v 中，则返回 True，否则返回 False。
"""
n = len(v)
k = len(v_prime)
if k > n:
return False
# 二分查找 v_prime 的第一个元素
left, right = 0, n - 1
first_element_index = -1
while left <= right:
mid = (left + right) // 2
if v[mid] == v_prime[0]:
first_element_index = mid
break # 找到第一个元素，退出循环
elif v[mid] < v_prime[0]:
left = mid + 1
else:
right = mid - 1
# 如果没有找到 v_prime 的第一个元素，则 v_prime 不存在于 v 中
if first_element_index == -1:
return False
# 线性验证剩余元素
for i in range(1, k):
if first_element_index + i >= n or v[first_element_index + i] != v_prime[i]:
return False
return True
# 示例
v = [-10, -3, 0, 4, 7, 19, 33]
v_prime = [4, 7, 19]
result = is_subarray_present(v, v_prime)
print(f"v_prime 是否存在于 v 中: {result}") # 输出: v_prime 是否存在于 v 中: True
v_prime2 = [4, 7, 20]
result2 = is_subarray_present(v, v_prime2)
print(f"v_prime2 是否存在于 v 中: {result2}") # 输出: v_prime2 是否存在于 v 中: False
v_prime3 = [-10]
result3 = is_subarray_present(v, v_prime3)
print(f"v_prime3 是否存在于 v 中: {result3}") # 输出: v_prime3 是否存在于 v 中: True
v_prime4 = [33,34]
result4 = is_subarray_present(v, v_prime4)
print(f"v_prime4 是否存在于 v 中: {result4}") # 输出: v_prime4 是否存在于 v 中: False时间复杂度分析
- 二分查找：O(log n)
- 线性验证：O(k)
总时间复杂度：O(log n + k)。由于通常情况下我们关注的是最坏情况，可以将其表示为 O(max(log n, k))。 当 n 远大于 k 时，时间复杂度接近 O(log n)。
注意事项
- 该算法要求两个数组都已排序。
- 线性验证部分假设子数组 v' 在 v 中是连续的。如果允许 v' 中的元素在 v 中不连续出现，则需要修改线性验证部分。
- 如果 v_prime 为空数组，根据实际需求，可以返回 True 或 False。上述代码返回 True。
总结
通过结合二分查找和线性验证，我们可以在 O(max(log n, k)) 的时间复杂度内，有效地判断一个排序子数组是否存在于一个更大的排序数组中。这种方法在处理大型数据集时，可以显著提高效率。
