Single Element in a Sorted Array - Solution & Explanation

Problem Overview: You are given a sorted array where every element appears exactly twice except one element that appears once. The task is to return that single element. The sorted property creates a predictable pairing pattern that allows more efficient solutions than a full scan.

Approach 1: Bitwise XOR (O(n) time, O(1) space)

The simplest solution relies on the XOR property: a ^ a = 0 and a ^ 0 = a. Iterate through the array and XOR every value with an accumulator. Since every duplicated element cancels itself out, the final value left in the accumulator is the single element. This approach ignores the sorted nature of the array and works for any array where every number appears twice except one. Implementation is extremely short and constant space, but the runtime is linear because you must scan every element.

Approach 2: Binary Search (O(log n) time, O(1) space)

The optimal solution leverages the sorted structure of the array together with binary search. In a correctly paired array, elements appear in pairs where the first index is even and the second index is odd (e.g., [a,a,b,b,c,c]). Once the single element appears, this pairing pattern breaks. During binary search, check whether mid forms a valid pair with its neighbor. If mid is even and nums[mid] == nums[mid+1], the single element lies to the right; otherwise it lies to the left. If mid is odd, compare with nums[mid-1]. Each step discards half of the search space, reducing the runtime to logarithmic time.

The key insight is that the single element shifts the index parity of every pair after it. Binary search detects where that shift occurs. Because the array is sorted and duplicates are adjacent, each comparison immediately tells you which half of the array still follows the valid pairing structure.

Recommended for interviews: The binary search solution is what interviewers typically expect because it exploits the sorted property and achieves O(log n) time. The XOR approach is still useful to mention first—it demonstrates awareness of bitwise tricks and works in the general case—but the optimized binary search shows stronger algorithmic reasoning and pattern recognition.