有序数组中的单一元素

笨办法谁都会：两两一组看，哪组对不上单的就在那。可数组百万长就慢了。题目特意给了「有序」这个条件，就是在提示你——能二分。

这是全题的命根子。单一元素像一根楔子插进队列，把它后面所有配对整体往右挤了一格，配对的「奇偶节奏」就此被打乱。下面用图把这个节奏画出来。

只要把 mid 永远对齐到偶数下标，再看它和下一格是不是一对：是一对，说明楔子还在右边；不是一对，说明楔子就在 mid 这里或更左。盯住下面 lo/hi/mid 三根指针怎么收缩。

看节奏 · 单一元素之前：先肉眼感受节奏。最左这一对 1、1：第一个 1 在下标 0(偶数)，它的搭档紧跟在下标 1。单一元素左边的每一对都这样——左半边在偶数位、右半边在奇数位。

看节奏 · 楔子出现：走到下标 2，2 找不到搭档——它就是那根楔子。从它往后(已变灰的部分)，所有配对被它顶得整体右移一格，奇偶节奏从这里被掰断。

看节奏 · 单一元素之后：看楔子右边的第一对 3、3：第一个 3 跑到了下标 3(奇数)！节奏反过来了——右半边在偶数位、左半边在奇数位。这个「奇偶翻转点」正是单一元素的位置，二分要找的就是它。

开局 · 二分范围：正式开二分。lo 指数组头(下标 0)、hi 指数组尾(下标 8)，单一元素一定落在这两根指针之间。我们要靠上面那条「偶数下标配对」规则，一轮轮把这个区间砍半。

第1轮 · 取 mid：取中点 mid=(0+8)/2=4。它正好是偶数下标，不用调整。规则要求 mid 必须落在偶数位，所以下一步要先检查这点。

第1轮 · mid 对齐偶数：mid=4 是偶数，直接拿它和右邻 arr[5] 组成一对(紫底窗口 [4,5])。如果 mid 是奇数，就要先 mid−1 退回偶数位再配对——这是不能省的一步。

第1轮 · 比这一对：arr[4]=3 和 arr[5]=4 对不上！偶数位的配对被打乱了，说明楔子就在 mid 这里或它左边。所以收右指针：hi = mid = 4，mid 本身可能是答案，不能丢。

第1轮 · 收 hi=mid：hi 收到 4，右半截下标 5~8 整段变灰出局。一刀砍掉一半，区间缩成 [0,4]。注意是 hi=mid 不是 mid−1，因为 mid=4 自己还可能就是楔子。

第2轮 · 取 mid：新区间 [0,4] 重新取中点，mid=(0+4)/2=2。又是偶数，省心。继续按规则配对。

第2轮 · 配对 [2,3]：mid=2 偶数，配上右邻成窗口 [2,3]，里头是 arr[2]=2 与 arr[3]=3。比一比这一对是否相等。

第2轮 · 比这一对：arr[2]=2 ≠ arr[3]=3，又没配上。和第 1 轮一个道理：偶数位配对乱了，楔子在 mid 或更左。再次收右指针 hi=mid=2。

第2轮 · 收 hi=mid：hi 收到 2，下标 3、4 再变灰出局。区间又砍半，缩成 [0,2]。两轮下来 9 个数只剩 3 个候选了。

第3轮 · 取 mid：区间 [0,2] 取中点，mid=(0+2)/2=1——这回是奇数！规则规定配对必须从偶数位起，所以这一步还不能直接比，得先把 mid 拨回偶数。

第3轮 · mid 退回偶数：mid 是奇数，执行 mid = mid−1 = 0，把它退回最近的偶数下标。现在 mid 指 0，可以放心配对了。这一步正是很多人写错二分的地方。

第3轮 · 配对 [0,1]：对齐后从 mid=0 配出窗口 [0,1]，里头是 arr[0]=1 与 arr[1]=1。这一对看起来很整齐，比一下。

第3轮 · 比这一对：arr[0]=1 == arr[1]=1，配上了！偶数位的配对完好，说明从这里到 mid+1 都是规规矩矩成对的，楔子在右边。所以推左指针 lo = mid+2 = 2，跳过这完整的一对。

第3轮 · 推 lo=mid+2：lo 跳到 2(跨过 0、1 这完整一对)，下标 0、1 变灰出局。现在 lo 和 hi 都指向 2，下一步它们就要撞上，二分该停了。

二分结束 · lo==hi==2：lo 和 hi 撞到一起，循环条件 lo<hi 不再成立，二分停下。区间收成单独一个下标 2——所有成对的数都被排除了，剩下的这一个孤点就是单一元素。

取出答案：返回 arr[2] = 2，正是那个落单的数。9 个元素只比了 3 轮配对就锁定，全程 O(log n)，没有一次多余的扫描。

雷区实演 · 楔子在右端：换个楔子靠右的例子 [3,3,7,7,10,11,11]：偶数位的 (0,1)、(2,3) 都配上 → lo 不断右推，最后停在下标 4，arr[4]=10。右边 11、11 又成对，刚好夹出 10。

边界三连：三种极端：长度 1、楔子在头、楔子在尾。lo<hi 的循环和「配上推右/没配上收左」天然把它们都兜住了。

面试追问：把「楔子打乱奇偶节奏」「mid 对齐偶数」讲透，再补一句异或法，是这题的面试加分项。