AlgoViz
HomeBinary Search

Single element in a Sorted Array

Medium

Pair parity tells you which side to keep

Problem

In a sorted array where every element appears exactly twice except one element that appears once, find that single element.

In simple words

Pairs sit at even-odd indices until the single breaks the pattern — binary-search that break.

The idea

Before the single element, every pair starts at an even index; after it, pairs start at odd indices. Checking whether the middle element still pairs with its even-indexed partner tells you which half contains the break.

The trick

  • Force mid to be even, then compare nums[mid] with nums[mid+1].
  • Equal means the single element is to the right; unequal means at mid or to the left.
  • O(log n), where a linear XOR scan would be O(n).
1
1
2
3
3
4
4
8
8
0
1
2
3
4
5
6
7
8

Step 1 of 4. Brute force: values come in pairs — walk two at a time until a pair breaks. Values: 1, 1, 2, 3, 3, 4, 4, 8, 8.

1/4
Brute force
timeO(n)spaceO(1)

Walk pairs.

1let single = -1;2for (let i = 0; i < n && single < 0; i += 2)3  if (nums[i] !== nums[i + 1]) single = nums[i];4return single;

Input

array
[1, 1, 2, 3, 3, 4, 4, 8, 8]

Memory

i
—

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output:
2
Explanation:
Every value is doubled except 2.

Example 2

Input:
nums = [3, 3, 7, 7, 10, 11, 11]
Output:
10
Explanation:
10 stands alone.

Example 3

Input:
nums = [1]
Output:
1
Explanation:
One element is the single.

Constraints

  • 1 <= n <= 10^5
  • n is odd
  • Every element but one appears exactly twice.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.