Single Element in a Sorted Array
A medium Binary Search interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Binary Search
- Sheets
- 1
- Core for
- 7 roles
The problem
In this sorted array every value appears twice in a row, except one value that appears only once. Find that value in O(log n) time and O(1) extra space.
Example 1
- Input
- nums = [2,2,5,5,6,7,7,8,8]
- Output
- 6
- Why
- Every element appears twice except 6 which appears once at index 4.
Example 2
- Input
- nums = [1,1,4,4,9,9,10,12,12]
- Output
- 10
- Why
- Every element appears twice except 10 which appears once at index 6.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^5
- nums.length is odd
How to think about it
Updated 2026-09-29Pairs before the single element always start on an even index and end on an odd index. The single element shifts the parity: every pair appearing after it starts on an odd index and ends on an even index. Checking index parity of any pair tells you which side contains the disruptor.
Approaches, worst first
Bitwise XOR scan
time O(n) · space O(1)
XOR all elements together; identical paired values cancel to zero, leaving the unpaired element. Operates in linear time without extra space, but fails to use the sorted property to achieve logarithmic speed.
Binary search on index parityWrite this one
time O(log n) · space O(1)
Probe mid and align it to an even index. If nums[mid] equals nums[mid + 1], the disruption has not happened yet, so search to the right (low = mid + 2); otherwise the unique item is at or to the left of mid (high = mid).
Where people lose marks · 3
- Accessing mid + 1 when mid is the final element triggers an index out-of-bounds exception unless the search interval bounds or even-index alignment prevent it.
- Setting high = mid - 1 on a pair mismatch skips the single element when mid itself is the unique item; keep high = mid.
- An input of length 1 should immediately return the only element without executing boundary pair checks.
The theory behind it
Binary Search — the ground this problem stands on. All Binary Search problems
What Binary Search is
Binary search is the guessing strategy used when searching a thick telephone directory or guessing a secret number between one and a hundred. Rather than inspecting names one by one from the first page, the search opens straight to the middle page. If the target precedes that middle entry, the entire back half is discarded; if it follows, the front half is eliminated. Repeating this halved split finds the item with remarkable speed.
When to reach for it
Reach for binary search when queries target sorted collections, rotated sorted arrays, or monotonic answer spaces. Strong hints include logarithmic time constraints like O(log n) or search ranges exceeding one billion where stepping one value at a time times out. It also applies when validating whether a guessed solution is possible via a monotonic boolean check, known as binary search on answer.
How the pattern works
Define the search territory with two inclusive pointers, low and high. Compute the midpoint using low plus half the difference to high, avoiding integer overflow. Formulate an exact boolean condition that divides the range into true and false halves. Decide whether the boundary condition includes the midpoint or shifts strictly past it. The loop invariant states that the sought target, if it exists, remains trapped inside the interval throughout every iteration.
More Binary Search problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .