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

Question

我的 friend 在考试中出了一道题，题目是:

You get an unsorted array with integer values as pairs , and 1 value as single for example:

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

The output is: 7

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

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

Answer 1

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

1. 拆分必须有 2n + 1 个元素的数组，如下所示:<n elements> <1 element> <n elements> :
2. 比较中间元素与第一部分的最后一个元素和第二部分的第一个元素:
   • 如果不等于，则已找到单个元素
   • 否则，将中间元素添加到具有相同元素的部分(如果它等于第一部分的最后一个元素，则将其附加到第一部分，否则将其作为第一部分添加第二部分的元素)
3. 对元素数量为奇数的部分重复上述步骤