Coding Interview PatternsSingle Element in a Sorted Array
MediumModified Binary Search
Single Element in a Sorted Array
Explanation & Solution
Description
Given a sorted array consisting of only integers where every element appears exactly twice except for one element which appears exactly once, find this single element.
Your solution must run in O(log n) time and O(1) space.
Input:nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
0
1
1
1
2
2
3
3
4
3
5
4
6
4
7
8
8
8
Output: 2
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^5- Every element appears exactly twice except for one element which appears once
Approach
Modified Binary Search pattern
1. Initialize Pointers
- Set
left = 0andright = nums.length - 1.
2. Align Mid to Even Index
- Compute
mid = (left + right) >> 1, then force it even:mid -= mid & 1. - This ensures we always check the first element of a potential pair.
3. Check if Pair Is Intact
- If
nums[mid] === nums[mid + 1], the pair atmidis intact → the single element is to the right. Setleft = mid + 2. - Otherwise, the single element disrupted pairs at or before
mid→ setright = mid.
4. Return the Single Element
- When
left === right, returnnums[left].
🧠 Key Insight
- In a sorted array of pairs, before the single element all pairs sit at (even, odd) index positions. After the single element, pairs shift to (odd, even). By forcing
midto an even index, we can check whether the pair pattern is intact.
Time
O(log n)binary search on pairs.Space
O(1).Visualization
Input:
[1, 1, 2, 3, 3, 4, 4, 8, 8]
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
9 steps