Single Element in a Sorted Array

The problem. You're given a sorted array in which every value appears exactly twice, except one value that appears once. Return that single value. Your solution must run in O(log n) time and O(1) space.

Example

nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]  ->  2
nums = [3, 3, 7, 7, 10, 11, 11]    ->  10
nums = [5]                         ->  5

The idea: the pairs shift at the single value

The array has an odd length, and pairs fill it two by two. Until the single value appears, every pair starts at an even index: nums[0] == nums[1], nums[2] == nums[3], …. The single value pushes everything after it one place right, so from there on pairs start at odd indexes. Take an even mid: if nums[mid] == nums[mid + 1], the pairs are still in step, so the single value is beyond this pair — low = mid + 2. If not, the shift already happened: the single value is at mid or before — high = mid.

1. XOR everything

a ^ a = 0 and 0 ^ b = b, so XOR-ing every value cancels the pairs and leaves the single one. It works on unsorted input too.

1function singleNonDuplicate(nums) {2  let x = 0;3  for (const v of nums) x ^= v;   // pairs cancel out4  return x;5}

Time O(n), space O(1). Neat, but it ignores the sorting and misses the O(log n) requirement.

2. Walk the pairs

1function singleNonDuplicate(nums) {2  for (let i = 0; i + 1 < nums.length; i += 2) {3    if (nums[i] !== nums[i + 1]) return nums[i];   // the first broken pair starts with the single one4  }5  return nums[nums.length - 1];                    // no broken pair: it's the last value6}

Time O(n), space O(1). This is the idea binary search speeds up: find the first broken pair.

3. Binary search on even indexes

1function singleNonDuplicate(nums) {2  let low = 0;3  let high = nums.length - 1;4  while (low < high) {5    let mid = low + Math.floor((high - low) / 2);6    if (mid % 2 === 1) mid--;                        // look at the start of a pair: an even index7    if (nums[mid] === nums[mid + 1]) low = mid + 2;  // pair intact: the single one is further right8    else high = mid;                                 // pair broken: the single one is at mid or before9  }10  return nums[low];11}

Time O(log n), space O(1). low and high stay even (both start even and move by even amounts), and the answer is always at an even index, so the range always holds it. mid + 1 is always a valid index because mid < high.

Comparing the approaches

Edge cases to test

Variations