Single Element in a Sorted Array
Every element in a sorted array appears exactly twice, except one element that appears once. Find it in O(log n) time and O(1) space.
- 1 <= nums.length <= 10⁵
- 0 <= nums[i] <= 10⁵
Intuition
Single element in a sorted array hides one unpaired value among pairs, and demands O(log n) time. That requirement is the real instruction: XOR-ing everything or scanning in steps of two both find the answer in O(n), and the problem is explicitly asking for better.
Logarithmic time means binary search, which needs a monotone signal — some property true on one side of the answer and false on the other. Sortedness alone does not provide it, since the array's values give no hint where the loner sits.
The signal is index parity. Before the single element, pairs sit at (even, odd) index positions: nums[0] == nums[1], nums[2] == nums[3], and so on. The unpaired element shifts everything after it by one, so pairs beyond it start on odd indices instead:
- At an even index mid, nums[mid] == nums[mid + 1] means the loner is to the right; otherwise it is at or to the left of mid.
That is monotone — pairing is intact left of the answer and broken right of it — which is exactly what binary search requires.
The implementation detail that makes it clean is forcing mid to be even, by clearing its low bit. Then the comparison always tests a pair start, and no separate case for odd midpoints is needed.
The loop ends when lo meets hi, and that position holds the single element.
Binary search on parity, not value. Before the single element, every pair starts at an even index; after it, that alignment breaks. Normalising mid to even and checking whether it pairs with mid + 1 tells you which side the anomaly lies on. Any problem where a property holds up to a point and then flips is binary-searchable.
Approach
Before reading on: price up what the direct approach costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(log n) time and O(1) space.
Read the complexity as the instruction
XOR or a linear scan solves this in O(n). The O(log n) requirement is what tells you to binary search — the problem is really asking you to find a monotone property, not just an answer.
Find the signal in index parity
Left of the loner, pairs occupy (even, odd) index pairs. The unpaired element shifts everything after it by one, so pairs to its right begin at odd indices. That break is the searchable boundary.
Force mid to be even
Clear the low bit of mid so it always lands on a pair start. This removes the need for a separate branch on odd midpoints and is what keeps the comparison uniform.
Compare mid with its partner
If nums[mid] == nums[mid + 1], pairing is still intact here, so the loner lies to the right — set lo = mid + 2. Otherwise it is at mid or to the left, so set hi = mid.
Keep the answer inside the window
The invariant is that the single element always lies within [lo, hi]. Moving hi to mid rather than mid - 1 preserves it — excluding mid could discard the answer itself.
Return when the window closes
When lo equals hi, that index holds the unpaired value. No final comparison is needed, since the invariant guarantees it.
Cost of the search
The window halves each iteration, giving O(log n) time and O(1) space — against O(n) for XOR, which is correct but ignores what the constraint was asking for.
Solution & live demo
Common pitfalls
Scanning linearly or XOR-ing everything
result = 0 for n in nums: result ^= n return result
while lo < hi:
mid = (lo + hi) // 2
if mid % 2 == 1: mid -= 1XOR gives the right answer but is O(n), and the problem explicitly asks for O(log n). The sortedness is the extra structure that makes a logarithmic solution possible.
Not normalising mid to an even index
if nums[mid] == nums[mid + 1]:
lo = mid + 2if mid % 2 == 1: mid -= 1
if nums[mid] == nums[mid + 1]:
lo = mid + 2The pairing argument only holds when comparing a pair's first element with its second. An odd mid compares across a pair boundary, so the parity test is meaningless and the search converges on the wrong half.
Using lo <= hi with hi = mid - 1
while lo <= hi:
...
else: hi = mid - 1while lo < hi:
...
else: hi = midmid itself may be the single element, so excluding it can step over the answer. Converging with lo < hi and keeping mid in range leaves lo sitting on it.
Edge cases
The very first pair test fails (nums[0] != nums[1]), so hi collapses to 0 immediately.
Every pair test passes; lo marches in steps of 2 to the final index.
Loop never runs (lo == hi already) — return the only element.