Single Element in a Sorted Array
Sorted array where every value appears twice except one — binary search on pair-aligned indices.
3 min read
binary-search
Problem#
Sorted array; all elements appear exactly twice except one. Return the unique element. O(log n).
Examples#
[1,1,2,3,3,4,4,8,8]→2
Constraints#
1 <= n <= 10^5,nis odd.
Approach#
Before the unique element, pairs start at even indices (a[2i] == a[2i+1]). After, pairs start at odd indices. Binary search on the parity of mid (force mid even via mid -= mid & 1); if a[mid] == a[mid+1], answer is to the right; else left.
Solution#
class Solution {public: int singleNonDuplicate(vector<int>& nums) { int lo = 0, hi = nums.size() - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (mid & 1) --mid; if (nums[mid] == nums[mid + 1]) lo = mid + 2; else hi = mid; } return nums[lo]; }};func singleNonDuplicate(nums []int) int { lo, hi := 0, len(nums)-1 for lo < hi { mid := lo + (hi-lo)/2 if mid&1 == 1 { mid-- } if nums[mid] == nums[mid+1] { lo = mid + 2 } else { hi = mid } } return nums[lo]}from typing import List
class Solution: def singleNonDuplicate(self, nums: List[int]) -> int: lo, hi = 0, len(nums) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if mid & 1: mid -= 1 if nums[mid] == nums[mid + 1]: lo = mid + 2 else: hi = mid return nums[lo]function singleNonDuplicate(nums) { let lo = 0, hi = nums.length - 1; while (lo < hi) { let mid = lo + ((hi - lo) >> 1); if (mid & 1) mid--; if (nums[mid] === nums[mid + 1]) lo = mid + 2; else hi = mid; } return nums[lo];}class Solution { public int singleNonDuplicate(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if ((mid & 1) == 1) mid--; if (nums[mid] == nums[mid + 1]) lo = mid + 2; else hi = mid; } return nums[lo]; }}function singleNonDuplicate(nums: number[]): number { let lo = 0, hi = nums.length - 1; while (lo < hi) { let mid = lo + ((hi - lo) >> 1); if (mid & 1) mid--; if (nums[mid] === nums[mid + 1]) lo = mid + 2; else hi = mid; } return nums[lo];}Editorial#
The parity trick exploits the structural invariant: pairs are aligned to even indices on the left of the unique element and to odd indices on the right. Snapping mid to even lets us compare against mid+1 consistently. The unique element acts as the “boundary” where pair alignment breaks.
Complexity#
- Time: O(log n).
- Space: O(1).
Concept revision#
Related#