在排序阵列中找到目标整数的次数的理论下限

Question

给定针对整数和目标整数的阵列，找到目标整数的出现次数。

众所周知，二进制搜索有时间复杂度 $ o（\ lg n）$ 其中 $ n$ 是数组的大小。 例如，给定数组 $ [1,2,3,3,4,5] $ 和目标 $ 3，$ 该算法应该返回 $ 2 $ ，因为阵列中有两个 $ 3 $ 中的两个副本。

问题：是否有更快的算法，该算法具有时间复杂度小于 $ o（\ lg n）？$ 否则，是否有证据证明 $ \ omega（\ lg n）$ 是理论下限？

Answer 1

问题需要 $ \ oomega（\ log n）$ 即使您承诺最多一次出现目标整数，也是如此访问内存。您可以使用对抗争论来证明它。

说目标为零。如果第一次访问阵列的左侧是中心，则应答 $ - 1 $ ，并在左边的元素设置为 $ - 2，-3，\ ldots $ 。如果第一个访问是中心的权利，则答案 $ + 1 $ ，并在精神上将元素设置为 $ 2 ，3，\ ldots $ 。

假设第一个访问是中心的权利，例如位置 $ i $ ，并考虑第二个访问。如果它在第一次访问权限的右侧，那么您已经知道要回答什么。否则，有两种情况。如果访问的位置 $ j $ 小于 $ i / 2 $ ，则答案 $ - 1 $ （并填充左侧的元素）。如果它超过 $ i / 2 $ ，则答案 $ + 1/2 $ （并填写Upgress到右边的Upile $ i $ ）。

以这种方式继续，在每个步骤中，每个步骤最多可包含目标元素的位置数最终。最后，当只有一个元素仍处于赌注时，在不查询它的情况下，算法无法确认阵列是否包含目标元素。它需要 $ \ log_2 n $ 步骤来达到此步骤。

前述实际上表明，二进制搜索是搜索排序阵列的最佳选择。

Answer 2

有 $ n $ 可能的答案。每个比较都为您提供最多的信息。您需要至少 $ \ lg n $ 信息来描述答案，因此您需要至少需要 $ \lg n $ 比较。