在 O(log n) 中搜索未排序数组中的值

Question

我的朋友在测试中遇到了一个问题，问题是：

您会得到一个未排序的数组，其中整数值作为pairs，1个值作为single，例如：

[1,1,5,5,2,2,4,4,7,12,12,8,8]

输出是：7

现在我知道二分搜索可以用O(log n)完成，但需要对数组进行排序。

那么如何在这个未排序的数组上以O(log n) 的时间完成呢？

Answer 1

如果值对彼此相邻，您还可以在未排序的数组中进行二分搜索：

1. 拆分必须具有 2n + 1 个元素的数组，如下所示<n elements> <1 element> <n elements>：：
2. 将中间元素与第一部分的最后一个元素以及第二部分的第一个元素进行比较：
   • 如果两者不相等，则已找到单个元素
   • 否则，将中间元素添加到具有相同元素的部分（如果等于第一部分的最后一个元素，则将其附加到第一部分，否则将其作为第一个元素添加到第二部分）
3. 对具有奇数个元素的部分重复这些步骤