Single Element in Sorted Array

Find the lone element that appears once in a sorted array where every other element appears twice.

binary-search array xor search

You are given a list `nums` of integers that has the following properties:
- The list is sorted in non-decreasing order.
- Every integer in the list appears exactly twice, except for exactly one integer that appears exactly once.
- The list has odd length.

Write a function `single_element(nums)` that returns the integer that appears exactly once.

Your solution must run in **O(log n)** time and **O(1)** space.

Constraints

1 <= len(nums) <= 100000
All integers in `nums` are in the range [-10^9, 10^9].

Example

>>> single_element([1,1,2,3,3,4,4,8,8])
2
>>> single_element([3,3,7,7,10,11,11])
10
>>> single_element([5])
5
>>> single_element([1,1,2,2,3])
3

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use binary search. Observe the parity of the mid index.

If `mid` is even, it should be the first occurrence of its pair; if `mid` is odd, it should be the second occurrence of its pair.

Compare `nums[mid]` with `nums[mid+1]` (or `nums[mid-1]`) to decide which side to search.

Alternatively, XOR all elements to get the answer in O(n), but that does not meet the time constraint.

The single element's index is always even. Use that to narrow the search.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.