Single Element in a Sorted Array: Binary Search on Index Parity
Solve Single Element in a Sorted Array in O(log n) with parity binary search — the intuition, JavaScript code, a full walkthrough, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Single Element in a Sorted Array (LeetCode 540) reads like a warm-up. Every value appears exactly twice except one — find that one. A hash map does it. XOR-ing everything does it in one line. Then you hit the last sentence of the prompt: your solution must run in O(log n) time and O(1) space.
That constraint is the real question. O(log n) means binary search — but there's no target value to search for, and no obvious "too high / too low" signal. Or so it seems.
The array is hiding a perfectly sorted signal after all: index parity. Before the single element, every pair starts at an even index. After it, every pair starts at an odd index. That flip is a boundary you can binary search, and the single element sits exactly on it.
The problem
You're given a sorted array nums where every element appears exactly twice, except for one element that appears exactly once. Return that single element in O(log n) time and O(1) space.
Input: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output: 2Two structural facts fall straight out of the statement:
- The array length is always odd — n pairs plus one singleton is 2n + 1 elements.
- Because the array is sorted, the two copies of each value are adjacent. Duplicates can't be scattered; they sit side by side.
That adjacency is what makes the parity trick possible.
The brute force baseline
Walk the array two elements at a time. Each hop should land on a matched pair; the first hop that doesn't has found the singleton.
function singleNonDuplicate(nums) {
for (let i = 0; i < nums.length - 1; i += 2) {
if (nums[i] !== nums[i + 1]) return nums[i];
}
return nums[nums.length - 1]; // singleton is the last element
}This is O(n) time — correct, simple, and exactly what the problem forbids. The popular XOR fold (nums.reduce((a, b) => a ^ b)) is also O(n): elegant bit math, but it has to touch every element, and it throws away the one property that makes this problem special — the array is sorted. Interviewers set the O(log n) bar specifically to see whether you'll exploit that.
The key insight: the singleton breaks index parity
Number the array 0, 1, 2, 3, ... and look at where pairs begin.
In a fully intact prefix — everything left of the single element — the first copy of each pair sits at an even index and its twin at the odd index right after: (0,1), (2,3), (4,5). The moment the singleton appears, it occupies one slot alone and shifts everything after it by exactly one position. From there on, pairs start at odd indices.
nums: [1, 1, 2, 3, 3, 4, 4, 8, 8]
index: 0 1 2 3 4 5 6 7 8
pairs: (0,1) ? (3,4) (5,6) (7,8) ← pairing flips from even-start to odd-start at index 2So define a test at any even index mid: is nums[mid] === nums[mid + 1]?
- Yes → the pairing is still intact through
mid + 1, so the singleton lies strictly to the right. - No → the pattern is already broken, so the singleton is at
midor somewhere to its left.
That test is monotonic: it answers "yes" for every even index left of the singleton and "no" at and after it. Finding the first "no" is the classic find-the-boundary binary search — the same shape as First Bad Version — which is why this pattern is called Parity Binary Search. One bonus fact makes the endgame clean: since every pair before the singleton fills an even+odd slot, the singleton itself always sits at an even index.
The optimal solution
This is exactly the algorithm the visualizer traces, line for line:
var singleNonDuplicate = function(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (mid % 2 === 1) mid -= 1; // normalize mid to an even index
if (nums[mid] === nums[mid + 1]) left = mid + 2; // pair intact → go right, skip the pair
else right = mid; // pattern broken → singleton at mid or left
}
return nums[left];
};Every line earns its place:
if (mid % 2 === 1) mid -= 1— the parity test only means something at a would-be pair start. Ifmidlands on an odd index, stepping back one puts it on the even index where a pair should begin, without ever leaving the search range.left = mid + 2— when the pair at(mid, mid + 1)matches, both of those slots are verified. Jumping past the whole pair keepslefteven and skips dead weight.right = mid, notmid - 1— when the values differ,miditself might be the singleton. Excluding it would let the answer escape the search window.while (left < right)— both bounds start even and every update keeps them even, so the window shrinks untilleft === right, pinned on the singleton's even index.return nums[left]reads it off.
No target, no comparisons against a value — the binary search runs entirely on a structural predicate.
Walkthrough: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
| Step | left | right | raw mid | even mid | nums[mid] vs nums[mid+1] | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 4 | 3 vs 4 — differ | pattern broken → right = 4 |
| 2 | 0 | 4 | 2 | 2 | 2 vs 3 — differ | pattern broken → right = 2 |
| 3 | 0 | 2 | 1 | 0 | 1 vs 1 — match | pair intact → left = 0 + 2 = 2 |
| 4 | 2 | 2 | — | — | loop exits | return nums[2] = 2 |
Step 3 shows both mechanisms at once: raw mid = 1 is odd, so it's normalized down to 0, and the intact pair (1, 1) proves the singleton lives to the right — left leaps over the entire pair to index 2. Nine elements, two comparisons, done. On a million-element array this takes about 20 iterations instead of a million.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Hash map counting | O(n) | O(n) | counts every element, then rescans for count 1 |
| Linear pair scan | O(n) | O(1) | checks pairs left to right until one breaks |
| XOR fold | O(n) | O(1) | must visit every element; ignores sortedness |
| Parity binary search | O(log n) | O(1) | one parity test halves the search window |
All three linear approaches are fine answers to a different problem (Single Number, where the array is unsorted). Here, sortedness plus adjacency of duplicates is a gift, and the parity search is the only approach that accepts it.
Common mistakes
- Testing
nums[mid] === nums[mid + 1]without forcingmideven. At an odd index that comparison straddles two different pairs, and the yes/no signal stops being monotonic — the search walks confidently to the wrong half. - Setting
right = mid - 1when the values differ. A mismatch means the break is atmidor earlier.miditself may be the singleton; shrink toright = mid, never past it. - Setting
left = mid + 1instead ofmid + 2. A match verifies two slots, not one. Advancing by one leaveslefton an odd index, breaking the even-bounds invariant the endgame depends on. - Using
while (left <= right). This template converges to a single index and reads the answer after the loop. Mixing in<=withright = midproduces an infinite loop the first time the window narrows to one element. - Reaching for XOR in the interview. It returns the right value and the wrong complexity class. If the interviewer wrote O(log n) in the prompt, the XOR fold is the trap, not the answer.
- Worrying about
nums[mid + 1]going out of bounds. It can't: whileleft < right, the floor of the midpoint is strictly less thanright, and normalizingmiddown only moves it further from the edge — somid + 1 ≤ rightalways holds.
Where this pattern shows up next
Parity search is one member of a family: binary searches that run on a derived signal instead of a raw target value.
- Binary Search — the canonical template this problem remixes; get the
left < rightvsleft <= rightdistinction solid here first. - Guess Number Higher or Lower — searching on oracle feedback instead of array values, the gentlest version of "no visible target."
- Sqrt(x) — binary search over an answer space rather than an array, judged by a computed predicate.
- Search in Rotated Sorted Array — another broken-invariant search, where you first decide which half is still "well-formed" before recursing into it.
To watch the parity test fire and the window collapse onto the singleton, step through it interactively — the visualizer shows the even-mid normalization and each half-elimination move by move.
FAQ
Why does mid have to be an even index?
Because the parity signal is defined at pair starts. Left of the singleton, pairs occupy (even, odd) index slots, so comparing an even index with the next index tests exactly one would-be pair. At an odd index, nums[mid] and nums[mid + 1] belong to two different pairs, and the comparison no longer tells you which side of the singleton you're on. Normalizing with if (mid % 2 === 1) mid -= 1 guarantees every test is meaningful.
Why does the solution jump left = mid + 2 instead of mid + 1?
When nums[mid] === nums[mid + 1] at an even mid, both indices are confirmed to be a matched pair, so the singleton must be strictly beyond mid + 1. Advancing by 2 skips the entire verified pair and — just as importantly — keeps left on an even index. Both bounds staying even is what lets the loop terminate with left === right sitting exactly on the singleton.
Can I just XOR all the elements instead?
For correctness, yes — XOR-ing everything cancels every pair and leaves the singleton. But it's O(n) time because it must read every element. This problem explicitly requires O(log n), which is only achievable by exploiting the sorted order through binary search. The XOR fold is the intended answer for Single Number (the unsorted variant), not for this one.
What are the time and space complexity of the parity binary search?
O(log n) time and O(1) space. Each iteration performs one parity check and one comparison, then discards roughly half of the remaining window — either everything up to and including a verified pair, or everything to the right of a detected break. A one-million-element array resolves in about 20 iterations, with only two integer variables of extra memory.
Does it work when the single element is at the very start or end?
Yes, with no special cases. For nums = [2, 3, 3, 4, 4], every parity test fails (the pattern is broken from index 0), so right walks down to 0 and the loop returns nums[0] = 2. For nums = [1, 1, 2, 2, 3], every test passes, so left climbs to the last index and returns nums[4] = 3. The boundary-search structure handles both extremes as ordinary cases.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.