Single Element in a Sorted Array
Medium · Binary Search · Array · Binary Search
Problem
You are given a sorted integer array nums in which every value appears exactly twice, except for one value that appears exactly once.
Return the value that appears only once. Your solution must run in O(log n) time and use O(1) extra space.
Examples
Input: nums = [2,2,5,7,7] Output: 5
5 is the only value without a partner.
Input: nums = [1,4,4,6,6,9,9] Output: 1
The single value can sit at the very start.
Input: nums = [8] Output: 8
A one-element array holds the answer directly.
Constraints
- 1 <= len(nums) <= 10^5 (always odd)
- 0 <= nums[i] <= 10^5
- nums is sorted in non-decreasing order
Approaches
- XOR every value — time O(n), space O(1)
Follow-up
What if every other value appears three times instead of two? The same idea works with groups: before the single value each group starts at a multiple of 3, so binary search for the first group whose first and third elements differ. See the use case “Single value among triples”.
Related problems
Start free on Cariara · Coding problems · System design studio
