在相邻重复元素的数组中找唯一非重复元素，能否实现O(logn)时间复杂度？

首先得明确一个关键前提：这个数组必须是有序的——你给的示例数组是有序的，这也是能实现O(logn)复杂度的核心条件，如果数组无序，那不可能做到比O(n)更快，毕竟你得至少看一遍所有元素才能确定哪个是唯一的。

核心思路：利用成对元素的下标规律 #

观察有序数组里的成对元素：

• 在唯一元素的左边，每一对的第一个元素下标是偶数（从0开始计数），第二个是奇数（比如示例里的8在0和1位，1在2和3位）
• 在唯一元素的右边，每一对的第一个元素下标是奇数，第二个是偶数（比如示例里的6在5和6位，2在7和8位）

我们可以用二分查找来利用这个规律，一步步缩小范围找到唯一元素。

具体实现步骤 #

1. 初始化左右指针：left = 0，right = len(arr) - 1
2. 当left < right时循环：
   • 计算中间位置mid，如果mid是奇数，把它减1调整为偶数（保证我们总是在一对元素的第一个位置开始比较）
   • 比较arr[mid]和arr[mid+1]：
     • 如果两者相等，说明唯一元素在mid+2的右侧，把left更新为mid + 2
     • 如果两者不等，说明唯一元素在mid的左侧（或者就是mid本身），把right更新为mid
3. 当循环结束时，left（此时left == right）就是唯一非重复元素的下标

用你的示例数组走一遍流程 #

示例数组：[8,8,1,1,4,6,6,2,2,9,9]，长度11

• 初始left=0，right=10
• 第一次循环：mid=(0+10)//2=5（奇数）→ 调整为4；arr[4]=4，arr[5]=6，两者不等 → right=4
• 第二次循环：left=0，right=4；mid=(0+4)//2=2（偶数）；arr[2]=1，arr[3]=1，两者相等 → left=2+2=4
• 此时left == right=4，循环结束，arr[4]=4就是我们要找的元素

时间复杂度分析 #

每次循环都把搜索范围缩小一半，所以时间复杂度是O(logn)，完全符合你的要求。

注意事项 #

• 数组必须是有序的，否则下标规律不成立
• 数组中必须只有一个唯一元素，其他元素都是成对出现的，不能有多个唯一元素或者不成对的情况

内容的提问来源于stack exchange，提问作者sneakysnake