Single Element in a Sorted Array

You are given a sorted array of integers nums in which every element appears exactly twice — except for one element, which appears exactly once.

Return the element that appears only once.

Your algorithm must run in O(log n) time and use O(1) extra space.

Hints

· Stuck? Reveal one nudge at a time.

The required O(log n) is a giant signpost: some yes/no question about the middle of the array must tell you which half holds the answer — and it is not a comparison of values.

Look at indices, not values. Before the single element, the first copy of every pair sits at an even index. What happens to that alignment after the single element appears?

At an even index i, test nums[i] == nums[i+1]. It is true for every even index before the single element and false from it onward — binary search that flip point, keeping mid on even indices and moving lo = mid + 2 or hi = mid.

Common doubts

The array length is odd (pairs contribute an even count, plus one). Every pair before the single element occupies an (even, odd) slot, so the single element lands on the next even index — and every pair after it starts on an odd index.

Then that element is the answer. In the binary search, lo == hi from the start, the loop never runs, and nums[0] is returned immediately.

XOR of all elements does cancel the pairs and leave the single one — but it reads every element, so it is O(n). The whole point of this problem is beating that with O(log n) by exploiting the sorted order.

No. While lo < hi, the midpoint (after stepping down to even) is strictly less than hi, so nums[mid + 1] is always in bounds.

Interview follow-ups

· What an interviewer asks next.

XOR all elements — pairs cancel and the single one survives, in O(n) time and O(1) space. Without order there is no structure to binary search, so O(n) is optimal.

Plain XOR no longer cancels. Count set bits per position modulo 3, or use the two-mask ones/twos trick — the Single Number II pattern. On a sorted array you could still binary search over index alignment in blocks of three.

XOR everything to get x XOR y, split elements into two groups by any set bit of that result, and XOR each group — the Single Number III pattern. In a sorted array, a pair-walk finds both in one pass.

Fun facts

The binary search here never asks which value is bigger — it only asks are these two neighbors equal. It is a search over index parity, not magnitude.
The skeleton — a guarantee that is intact on a prefix and broken on the suffix, binary searched at its flip point — is the same one that solves finding the first bad version, searching rotated arrays, and finding a peak element.

Asked at

AmazonGoogleMicrosoftAdobe

Frequently Sometimes Occasionally

Example 1

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
Every value pairs up except 2 — 1, 3, 4, and 8 all appear twice.

Example 2

Input: nums = [3,3,7,7,10,11,11]
Output: 10
10 is the only value with no partner.

Constraints

- 1 <= nums.length <= 10^5 - 0 <= nums[i] <= 10^5 - nums is sorted in non-decreasing order - Every element appears exactly twice, except for one element which appears exactly once

A sorted array where every value has a twin — except one. Finding the loner in O(n) is easy; the real lesson is that the pairing structure itself can be binary searched, no value comparisons needed. Searching a property instead of a value is one of the most reusable tricks in interviews.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary search on a predicate. Halving a range using a yes/no question that is true on one side of a boundary and false on the other — not just hunting for a value.

Index parity. Knowing which indices are even and odd, and how inserting one extra element shifts everything after it by one.

Loop invariants. Keeping a promise like lo and hi always rest on even indices true across iterations is what makes the pointer moves safe.

Understand the problem

In plain English: the array is sorted, all values come in adjacent pairs, one value has no partner — return it. Formally: given nums sorted in non-decreasing order where exactly one element appears once and every other element appears exactly twice, return the element that appears once, in O(log n) time and O(1) space.

Worked example — nums = [1,1,2,3,3,4,4,8,8]

index : 0  1  2  3  4  5  6  7  8
nums  : 1  1  2  3  3  4  4  8  8
        └──┘  ↑  └──┘  └──┘  └──┘
        pair  2   pairs now start on ODD indices
answer: 2  (the only value with no partner)

Clarifying questions

Asking two or three sharp questions before coding shows you code from guarantees, not hope.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is the array guaranteed to be sorted, with exactly one element appearing once and everything else exactly twice?”

Everything below leans on this structure. Without sortedness the two copies are not adjacent, and you fall back to XOR or a hash map in O(n).

“Can the array be empty?”

No — the length is at least 1. With a single element, that element is the answer.

Edge cases

“Can the single element sit at the very front or the very back?”

Yes — think of [2, 3, 3] and [1, 1, 2]. Your boundary handling must survive both.

“What should happen when n equals 1?”

Return the lone element immediately; a correct binary search does this for free because the loop never runs.

Constraints and scale

“How large can n get, and is O(n) acceptable?”

Up to 10^5, so a linear scan would pass a judge — but the statement demands O(log n), and meeting it is the actual interview signal.

The ideal opening — say it like this

Before I code, let me confirm the structure: the array is sorted, and exactly one element appears once while every other element appears exactly twice — correct?

Then the two copies of any value are always adjacent, and the single element could also sit at index 0 or at the very end.

Since you are asking for O of log n on a structural guarantee, I will binary search the point where the pairing pattern breaks rather than the values themselves.

Key observations

1Aha

The single element always sits at an even index

Pairs contribute an even count, plus one single — so n is always odd. Every pair before the single element occupies an (even, odd) slot, which forces the single element onto the next even index.

index : 0  1  2  3  4  5  6
nums  : 3  3  7  7  10 11 11
        └──┘  └──┘  ↑
   even-start pairs │ single at index 4 (even)

2Aha

One yes/no question flips exactly once across the array

At any even index i, ask: is nums[i] == nums[i + 1]? Before the single element the answer is always yes (pairs start even); at and after it the answer is always no (pairs start odd). True, true, …, false, false — a monotone predicate with a single flip point, and that flip point is the single element.

3Aha

A monotone predicate is a binary search invitation

Check the middle even index. Pair intact → the break is strictly to the right, so jump lo = mid + 2. Pair broken → the single element is here or to the left, so pull hi = mid. Each question halves the remaining candidates: O(log n).

Brute force vs optimal

	Brute force	Optimal
Time	O(n)	O(log n)
Space	O(1)	O(1)
Idea	walk the pairs left to right	binary search the even-index pairing

Both are worth knowing — the pair-walk is the mental model, and the binary search compresses it. Full code for each lives in the Approaches selector below.

Summary

Key takeaway

Binary search does not need sorted values — it needs any property that is all-true then all-false across the array. Here the property is pairs still start on even indices, and its flip point is the answer. Spot a guarantee, turn it into a monotone yes/no question, and O(n) becomes O(log n).

lo, hi = 0, n - 1
while lo < hi:
    mid = (lo + hi) / 2, stepped down to an even index
    if nums[mid] == nums[mid + 1]: lo = mid + 2   # pairs intact → loner is to the right
    else:                          hi = mid       # pattern broken → loner is here or left
return nums[lo]