algorithm - 搜索组合的 2 排序数组

Question

算法能否在 O( log(n) ) 中搜索组合的 2 排序数组？？

组合 2 个排序数组:
是 2 个排序数组的组合..
例子: {1,2,3,4,5} + {2,3,4,5,6,7,} = {1,2,3,4,5,2,3,4,5,6,7}
不幸的是，你不知道它们的边界

*请注意，我知道一个解决方案可以在摊销时间内给出 O( log(n) )，但我只需要一次搜索就需要 O( log(n) )..

编辑:您可以假定不同的元素

谢谢

Answer 1

我认为在最坏的情况下，您必须检查组合数组的每个元素，这给出了 O(n) 最坏情况的复杂度。

直觉是这样的:假设您检查了元素的某些子集，发现它们随位置单调递增，而您要查找的元素不在该子集中。您绝对无法放弃部分搜索空间，因为该元素 - 无论其大小如何 - 仍然可以有效地位于任何未检查的位置。在最坏的情况下，在您检查整个阵列之前，这种情况可能一直为真。