Single Element in a Sorted Array
Problem
A sorted array contains pairs of equal elements except for one single element that appears once. Find the single element in O(log n) time.
nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]2def single_non_duplicate(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] == nums[mid ^ 1]:
lo = mid + 1
else:
hi = mid
return nums[lo]function singleNonDuplicate(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === nums[mid ^ 1]) lo = mid + 1;
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) >>> 1;
if (nums[mid] == nums[mid ^ 1]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}
}int singleNonDuplicate(vector<int>& nums) {
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] == nums[mid ^ 1]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}Explanation
Every value appears twice except one loner. We could scan the array, but the sorted layout lets us pin down the single element in O(log n) with a clever binary search on parity (even/odd indices).
Here is the key observation: before the single element, each pair starts at an even index — so index 0,1 hold a pair, 2,3 hold the next, and so on. After the loner, that alignment shifts and pairs start at odd indices. So the loner is the boundary where the pattern breaks.
The trick mid ^ 1 turns an even mid into mid + 1 and an odd mid into mid - 1 — it points at mid's expected partner. If nums[mid] == nums[mid ^ 1], the pair is intact and the loner is to the right (lo = mid + 1); if not, the pattern already broke at or before mid, so the loner is at mid or to its left (hi = mid).
Example: nums = [1,1,2,3,3,4,4,8,8]. Early on the pairs line up at even indices, but at the single 2 the partner check fails, and the search converges on its index, returning 2.
Each step halves the array, so we find the lonely element with about log n checks rather than scanning all of it.