Single Element in a Sorted Array
Find the one value that appears once in a sorted array of pairs in O(log n): binary search on whether the pair at an even index is still intact.
Problem Understanding
Single Element in a Sorted Array: in a sorted array, every element appears exactly twice except one, which appears once. Return that single element in O(log n) time and O(1) space.
Examples: [1,1,2,3,3,4,4,8,8] returns 2; [3,3,7,7,10,11,11] returns 10.
The Intuition: The Single Shifts the Pairs
Look at where pairs start:
- Left of the single, pairs sit at
(0,1), (2,3), (4,5), ...: every pair starts at an even index. - Right of the single, everything is shifted by one, so pairs start at odd indexes.
- So at an even
mid,nums[mid] == nums[mid + 1]means "still aligned": the single is to the right. Otherwise it is atmidor to the left.
Each comparison halves the range, a binary search on a yes/no property rather than on the values themselves, like Find Peak Element and First Bad Version. Without the sorted order, the XOR trick from Single Number would be the best you could do, in O(n).
Interactive Walkthrough
mid IS ALWAYS EVEN · TINTED = mid + 1
FULL RANGE
lo
0
1
2
3
4
5
6
7
hi
8
lo
0
hi
8
single
:
lo = 0, hi = 8. Before the single, pairs start at even indexes; after it, at odd ones
Next
mid = 4. nums[4] = 3 ≠ nums[5] = 4: the alignment broke at or before 4. hi = 4
nums
The array shows lo, mid and hi; cells outside the range are struck out. mid is solid and its partner mid + 1 is tinted. Try Single first to see every check send the search left.
Dry Run Table
Input: [1,1,2,3,3,4,4,8,8]
| lo | hi | mid (even) | Pair | Move |
|---|---|---|---|---|
| 0 | 8 | 4 | 3 ≠ 4 | hi = 4 |
| 0 | 4 | 2 | 2 ≠ 3 | hi = 2 |
| 0 | 2 | 1 → 0 | 1 = 1 | lo = 2 |
Answer: lo = hi = 2, so nums[2] = 2.
The Solution Template
Binary search with lo < hi. Moving lo past the whole intact pair (mid + 2) keeps lo on an even index.
Single Element in a Sorted Array Code
1var singleNonDuplicate = function(nums) {2 let lo = 0, hi = nums.length - 1;3 while (lo < hi) {4 let mid = Math.floor((lo + hi) / 2);5 if (mid % 2 === 1) mid--;6 if (nums[mid] === nums[mid + 1]) lo = mid + 2;7 else hi = mid;8 }9 return nums[lo];10};
Edge Cases & Common Mistakes
- One element:
lo == hifrom the start; return it. - Single at either end: works without special cases; the search just keeps moving one way.
- Comparing at an odd mid:
nums[mid] == nums[mid + 1]then means the opposite; snap to even first (or compare withmid ^ 1). lo = mid + 1: lands on an odd index and breaks the alignment rule; skip the whole pair withmid + 2.- XOR or a hash map: correct but O(n).
Summary
Pairs start at even indexes before the single and odd ones after. Snap mid to even; if nums[mid] == nums[mid + 1], move lo to mid + 2, otherwise hi = mid. Return nums[lo]. O(log n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet