解題說明
Single Element in a Sorted Array
題目描述： 給定一個排序陣列，其中每個元素都出現恰好兩次，只有一個元素出現一次。找出那個只出現一次的元素。要求 O(log n) 時間和 O(1) 空間。
解題思路：
利用二分搜尋與配對位置的關係。在單獨元素之前，配對的起始索引為偶數（即 nums[0]==nums[1], nums[2]==nums[3], ...）。在單獨元素之後，配對起始索引變為奇數。
- 對偶數索引進行二分搜尋。
- 取
mid（確保為偶數）：- 若
nums[mid] == nums[mid+1]，代表左邊的配對完整，單獨元素在右邊 →left = mid + 2。 - 否則，單獨元素在 mid 或其左邊 →
right = mid。
- 若
- 當
left == right時，nums[left]即為答案。
C++ 解法
複雜度分析
時間複雜度：O(log n) — 每次迭代排除一半的搜尋空間。
空間複雜度：O(1) — 只使用常數個變數。
虛擬碼
1. Initialize left = 0, right = n - 1 2. While left < right: a. mid = left + (right - left) / 2 b. If mid is odd, decrement mid (ensure even index) c. If nums[mid] == nums[mid + 1]: left = mid + 2 (single is right) d. Else: right = mid (single is at mid or left) 3. Return nums[left]
其他解法
XOR 法 O(n)：對所有元素做 XOR，由於 a ^ a = 0，所有成對元素互消，剩下的就是單獨元素。時間 O(n)，空間 O(1)。簡單但不利用排序性質，無法達到 O(log n)。
標準二分搜尋（不強制偶數 mid）：比較 nums[mid] 與其左右鄰居，根據 mid 的奇偶性和配對情況判斷方向。邏輯需要更多分支，但本質相同。強制 mid 為偶數可以簡化判斷邏輯。
延伸思考
- 為什麼要確保 mid 是偶數索引？如果 mid 是奇數，判斷邏輯會如何改變？
- 若陣列未排序，能否在 O(log n) 時間內解決？為什麼排序是 O(log n) 解法的關鍵？
- 若有兩個元素各出現一次（其餘出現兩次），能否用 O(log n) 時間找出？需要什麼額外條件？