有序数组中只有一个元素出现一次，为什么能用二分找出来？

简化版

有序数组里除一个元素出现一次外，其余都出现两次。单一元素出现前，成对元素的第一个位置在偶数下标、第二个在奇数下标；单一元素出现后，这个奇偶规律会被打乱。二分时把 mid 调成偶数，只比较 nums[mid] 和 nums[mid+1]：相等说明单一元素在右边，否则在左边含 mid，最终 lo 就是答案。

详细版

规律来自有序数组的成对相邻。正常配对时 (0,1)、(2,3)、(4,5) 都是相等对；一旦某处插入了单一元素，后面的配对会变成 (奇数,偶数)。因此可以用二分判断当前偶数下标对是否完整。

int singleNonDuplicate(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if ((mid & 1) == 1) mid--; // 保证 mid 是一对的左端
        if (nums[mid] == nums[mid + 1]) lo = mid + 2;
        else hi = mid;
    }
    return nums[lo];
}

每轮至少排除半边，时间 O(log n)，空间 O(1)。面试重点是说明为什么 mid 要对齐到偶数下标，以及为什么相等时可以跳过这一整对。

完整版教学

一、排序让重复元素必然相邻

题目给的是有序数组，所以出现两次的元素一定相邻。若数组无序，两个相同元素可能分散在各处，二分就没有结构可用，只能用异或或哈希。有序这个条件把“找单独元素”变成了“找配对规律被破坏的位置”。

例如 [1,1,2,3,3,4,4,8,8]，答案是 2。答案之前的 1,1 正常成对；答案之后的 3,3 虽然仍相邻，但它们的起始下标从偶数变成了奇数。这个下标奇偶变化就是二分的抓手。

正常前缀：index 0,1 -> 1,1
单一元素：index 2 -> 2
后缀错位：index 3,4 -> 3,3

二、成对规律是什么

在单一元素出现之前，每一对的左端下标都是偶数，右端下标都是奇数：nums[0]==nums[1]、nums[2]==nums[3]。这是因为前面没有多出来的元素，配对从下标 0 开始，每对占两个位置。

单一元素出现后，后面的所有对整体右移一位，所以对的左端变成奇数，右端变成偶数。换句话说，我们要找的就是“偶数下标配对失败”的最早位置附近。这个规律比记模板重要，能帮助解释每次排除半边为什么安全。

区域	配对形态	例子
答案左侧	偶数-奇数成对	`(0,1),(2,3)`
答案位置	单独占一格	`mid`
答案右侧	奇数-偶数成对	`(5,6),(7,8)`

记忆钩子：单一元素像往队伍里插了一格，把它右边所有配对的奇偶节奏打乱。

三、为什么 mid 要调整成偶数

二分时我们希望 mid 指向一对的左端，然后比较 nums[mid] 和 nums[mid+1]。若 mid 是奇数，它可能是一对的右端，直接和右边比较会错位。因此常见写法是如果 mid 为奇数，就 mid--，把它拉回偶数下标。

例如数组 [1,1,2,3,3]，若 mid=1，nums[1]=1，它是第一对的右端，和 nums[2]=2 比较当然不相等，但这不能说明答案在左边。把 mid 调成 0 后，比较 nums[0] 和 nums[1] 才是在检查完整的一对。

if ((mid & 1) == 1) mid--;

四、相等时为什么答案在右边

当 mid 是偶数且 nums[mid] == nums[mid+1]，说明从当前位置看这一对是完整的。由于 mid 左侧的区间长度也是偶数，配对规律到 mid+1 都没有被破坏，所以单一元素不可能在这一对或它左边，答案只能在 mid+2 到 hi。

带数字例子：[1,1,2,3,3,4,4]，若 mid=0，nums[0]==nums[1]，那么 1 这一对完整，可以跳过。剩下 [2,3,3,4,4] 继续找。跳过两个位置而不是一个，是因为这一对已经被证明不是答案。

mid 偶数且 nums[mid]==nums[mid+1]
=> [lo..mid+1] 配对完整
=> lo = mid + 2

五、不相等时为什么答案在左边含 mid

当 mid 是偶数但 nums[mid] != nums[mid+1]，说明偶数-奇数配对在 mid 这里失败。失败有两种可能：nums[mid] 就是单一元素，或者单一元素在更左边导致这里已经错位。不管哪种，答案都在 [lo..mid]，所以 hi = mid。

例如 [1,1,2,3,3]，mid=2，nums[2]=2、nums[3]=3，不相等，答案就是 mid。再如 [1,2,2,3,3]，mid=2 时若对齐比较会发现前面已经错位，答案在左侧。把 hi 收到 mid 是安全的。

mid 偶数且 nums[mid]!=nums[mid+1]
=> 配对规律已被破坏
=> 答案在左半，包括 mid

六、边界和复杂度

数组长度一定是奇数，因为成对元素贡献偶数个，再加一个单一元素。循环条件 lo < hi 保证 mid+1 不会越界：当 lo==hi 时已经收敛，不再比较。单元素数组 [1] 会直接返回 nums[0]。

每轮通过配对判断排除大约一半搜索空间，所以时间是 O(log n)，空间 O(1)。这比异或 O(n) 更快，但依赖有序数组和“其他元素恰好两次”这两个前提。若前提变化，二分规律也会失效。

方法	时间	空间	前提
异或	O(n)	O(1)	其他元素出现两次
二分奇偶	O(log n)	O(1)	数组有序且成对相邻

七、常见误区与追问

误区：直接比较 nums[mid] 和 nums[mid-1]。 mid 可能落在对的左端或右端，方向不统一会让边界混乱。
误区：mid 不需要调偶数。 不对齐到对的左端，比较对象可能不是同一对。
误区：相等时只令 lo=mid+1。 已经确认一整对不是答案，应跳到 mid+2。
追问：为什么异或也能做？ 成对元素异或抵消，剩下单一元素，但它是 O(n)，没有利用有序性。
追问：如果其他元素出现三次怎么办？ 奇偶配对规律失效，需要按位统计或其他方法。
追问：如果数组无序怎么办？ 二分前提不存在，可用异或、哈希或排序后再处理。

八、加强记忆

这题的核心不是找数值，而是找“配对节奏被打断的位置”。答案左边是偶奇成对，答案右边配对整体错一位。二分时把 mid 拉到偶数下标，比较它和右邻；相等就跳过完整一对，不等就把答案留在左半含 mid。这个奇偶不变量一清楚，代码就不容易写错。

简化版

详细版