Single Element in a Sorted Array — Solution

Problem

You are given a sorted array of integers where every value appears exactly twice — except for one value that appears exactly once. Find and return that unique element. Your solution must run in O(log n) time and use O(1) extra space.

• Input: [1, 1, 2, 3, 3, 4, 4, 8, 8]
• Output: 2
• Explanation: Every element except 2 appears twice; 2 is the unique single element.

Counter-example: [3, 3, 7, 7, 10, 11, 11] — the pairs stop aligning at even indices after position 4, revealing that 10 at index 4 is the single element.

Intuition

Because every value appears twice, the pairs in the sorted array start out aligned at even indices (index 0 and 1, then 2 and 3, and so on). The single element breaks this alignment: everything to its right is shifted by one, so pairs now straddle odd/even boundaries. Binary search can detect this shift at any midpoint without scanning the entire array.

Approach 1 — XOR Scan

XOR every number together. Paired values cancel out (x ^ x = 0), leaving only the single element (x ^ 0 = x). No sorting structure is exploited, but the code is remarkably short.

1. Initialize result = 0.
2. XOR every element in the array into result.
3. Return result.

1def singleNonDuplicate(nums: list[int]) -> int:
2    result = 0
3    for num in nums:
4        result ^= num  # paired values cancel; only the unique one survives
5    return result

Time: O(n) — visits every element once.
Space: O(1) — only a single integer accumulator.

Approach 2 — Binary Search on Pair Alignment

Before the single element, nums[even_index] == nums[even_index + 1]. After it, the pairing is off — nums[even_index] != nums[even_index + 1]. Snap the midpoint to an even index and check which side of the boundary we are on.

1. Set lo = 0, hi = len(nums) - 1.
2. While lo < hi: compute mid; if mid is odd, subtract 1 to make it even.
3. If nums[mid] == nums[mid + 1], the pair at mid is intact — single element is to the right, so lo = mid + 2.
4. Otherwise, the pair is broken — single element is at mid or to the left, so hi = mid.
5. Return nums[lo].

1def singleNonDuplicate(nums: list[int]) -> int:
2    lo, hi = 0, len(nums) - 1
3    while lo < hi:
4        mid = (lo + hi) // 2
5        if mid % 2 == 1:
6            mid -= 1  # always evaluate at an even index so pair-check is meaningful
7        if nums[mid] == nums[mid + 1]:
8            lo = mid + 2  # pair is intact; single element lies further right
9        else:
10            hi = mid  # pair broken here; single element is at mid or to its left
11    return nums[lo]

Time: O(log n) — halves the search space each iteration.
Space: O(1) — only two pointers.

Complexity Summary

Common Mistakes

• Checking the wrong neighbor after adjusting mid: After snapping mid down to even, always compare nums[mid] with nums[mid + 1] — comparing with nums[mid - 1] instead gives wrong results because mid - 1 may be the other half of a pair from the left region.
• Setting lo = mid + 1 instead of lo = mid + 2: When nums[mid] == nums[mid + 1], both indices belong to a complete pair that lies before the single element — you must skip both, not just one.
• Forgetting to snap mid to even: If mid is odd, nums[mid] is the second element of a pair. The pair-alignment rule (nums[even] == nums[even + 1] before the single element) only holds at even starting indices, so checking from an odd index gives a misleading result.
• Accidentally going out of bounds: When mid is the last even index (e.g., mid == len - 1), nums[mid + 1] would be out of bounds. Anchoring hi to the last element and only snapping mid down (never up) keeps mid + 1 always valid while lo < hi.
• Applying XOR when O(log n) is required: XOR is elegant but O(n). If the interviewer specifies logarithmic time — as this problem does — the XOR solution will not be accepted even though it produces the correct answer.

Related Problems

• Binary Search — foundational template this solution extends
• Find Peak Element — binary search guided by a local structural property rather than a target value
• Find Minimum in Rotated Sorted Array — uses array structure (sorted with a rotation point) to decide which half to discard
• Search in Rotated Sorted Array — binary search where the invariant is not simple monotonicity
• Koko Eating Bananas — binary search on a numeric property rather than an array position