我有一个问题，我试图一遍又一遍地思考...但是什么也没有，所以在这里发布了问题。也许我可以了解其他人的观点，尝试使其发挥作用...
问题是:我们得到了一个SORTED数组，它由一组值组成，这些值的出现次数为偶数次，唯一的一次是奇数次。我们需要在n天内找到解决方案。
在O(n)时间内很容易找到解决方案，但是在log n时间内执行起来似乎很棘手。
最佳答案
定理:在最坏的情况下，用于此问题的每种确定性算法都会探查Ω(log2 n)存储位置。
证明(以更正式的样式完全重写):
令k> 0为奇数整数，令n = k2。我们描述了一个强制(log2(k + 1))2 =Ω(log2 n)探针的对手。
我们称相同元素组的最大子序列。对手的可能输入包括k个长度为k的段x1 x2…xk。对于每个分段xj，存在一个整数bj∈[0，k]，使得xj由j-1的bj个副本组成，后跟j的k-bj个副本。每个组最多重叠两个分段，每个段最多重叠两个组。
Group boundaries
| | | | |
0 0 1 1 1 2 2 3 3
| | | |
Segment boundaries
凡增加两个，按照惯例，我们都假定为双重边界。
Group boundaries
| || | |
0 0 0 2 2 2 2 3 3
声明:第j个组边界(1≤j≤k)的位置由段xj唯一确定。
证明:就在第((j-1)k + bj)个存储位置之后，并且xj唯一确定bj。 //
我们说，如果xj的探测结果唯一确定xj，则该算法已观察到第j组边界。按照惯例，始终观察输入的开始和结束。该算法有可能在不观察的情况下唯一确定组边界的位置。
Group boundaries
| X | | |
0 0 ? 1 2 2 3 3 3
| | | |
Segment boundaries
仅给定0 0？，该算法无法确定是否为？。是0或1。但是，在上下文中，？必须为1，否则将存在三个奇数组，并且可以推断X处的组边界。这些推论对于对手来说可能是有问题的，但是事实证明，只有在所讨论的群体边界是“不相关的”之后才能做出推论。
声明:在算法执行过程中的任何给定时间点，都要考虑它观察到的一组组边界。恰好一对连续的对处于奇数距离，并且奇数组位于它们之间。
证明:每隔两个连续的对仅限制偶数组。 //
将以特殊连续对为边界的奇数长度子序列定义为相关子序列。
声明:在相关子序列内部没有唯一确定组边界。如果存在至少一个这样的边界，则不能唯一地确定奇数组的身份。
证明:在不失一般性的前提下，假设已探查了不在相关子序列中的每个存储位置，并且包含在相关子序列中的每个段都具有一个尚未被检测的位置。假设第j个组边界(称为B)位于相关子序列的内部。通过假设，xj的探针最多确定B个位置的两个连续可能性。我们称其为离左观察边界奇数距离的奇数左和另一个奇数右。对于这两种可能性，我们从左到右进行工作，并固定每个剩余内部组边界的位置，以使左侧的组均匀。 (我们之所以这样做，是因为它们每个人都有两个连续的可能性。)如果B在奇数左，则其左的组是唯一的奇数组。如果B在奇数右，则相关子序列中的最后一组是唯一的奇数组。两者都是有效输入，因此该算法既没有唯一确定B的位置，也没有唯一确定奇数组的位置。 //
例:
Observed group boundaries; relevant subsequence marked by […]
[ ] |
0 0 Y 1 1 Z 2 3 3
| | | |
Segment boundaries
Possibility #1: Y=0, Z=2
Possibility #2: Y=1, Z=2
Possibility #3: Y=1, Z=1
作为此主张的结果，该算法无论其如何工作，都必须将相关子序列缩小为一组。因此，根据定义，它必须遵守某些组边界。对手现在的任务很简单，就是尽可能地保持开放。
在算法执行过程中的任何给定时刻，对手都会在内部致力于相关子序列之外的每个内存位置的一种可能性。最初，相关的子序列是整个输入，因此没有初始 promise 。每当算法探测到xj的未提交位置时，对手就必须使用以下两个值之一:j-1或j。如果可以避免遵守第j个边界，则选择一个至少保留剩余可能性一半(相对于观察)的值。否则，它选择将至少一半的组保留在相关间隔中，并提交其他组的值。
这样，对手迫使算法观察至少log2(k +1)个组边界，并且在观察第j组边界时，该算法被迫进行至少log2(k +1)个探针。
扩充功能:
通过将输入随机化，将“最好减半”(从算法的 Angular 来看)替换为“期望减半”，并应用标准浓度不等式，此结果可直接扩展到随机算法。
它也扩展到任何组都不能大于s个副本的情况；在这种情况下，下限是Ω(log n log s)。