c++ - 在连续重复元素的数组中查找单个元素

给定一个元素数组，其中除单个元素外，每个元素都重复。而且所有重复的元素都是连续的。
我们需要找出那个元素的索引。
笔记
数组不能排序
预期时间o（logn）
元素范围可以
什么都可以。
o（n）是微不足道的。但我怎么能搞清楚洛根？
也考虑了按位运算符，但没有结果。
另外，我不能在这个问题上利用这句话，所有重复的元素都是连续的。

Ex:  2 2 3 3 9 9 1 1 5 6 6
     output 5

最佳答案

可以在o（logn）中通过检查是否arr[2k] == arr[2k+1], k>=0-如果是，则不同元素在2k+1之后，如果不是-则在2k+1之前。
这允许您通过检查中间值在每一步有效地修剪数组的一半，并且只在问题一半大的情况下递归，得到它的整体O(logn)。
Python代码：

def findUnique(arr,l,r):
    if r-l < 2:
        return (arr[l],l)
    mid = (r-l)/2 + l
    if mid % 2 != 0:
        flag = -1
    else:
        flag = 0
    if (mid == 0 or arr[mid-1] != arr[mid] ) and (mid == len(arr)-1 or arr[mid] != arr[mid+1] ):
        return (arr[mid],mid)
    if arr[mid+flag] == arr[mid+1+flag]:
        return findUnique(arr,mid,r)
    return findUnique(arr,l,mid)

关于c++ - 在连续重复元素的数组中查找单个元素，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31349334/