407. Single Element in a Sorted Array
You receive a sorted array of integers nums in which every value appears exactly twice — except for one value, which appears exactly once. Return that lone value.
A linear scan is easy; the real assignment is to exploit the sorted, everything-paired structure and find the answer in O(log n) time and O(1) space.
Example 1:
Input: single_non_duplicate([1, 1, 2, 3, 3, 4, 4, 8, 8])
Output: 2
Explanation: Every value pairs up (1, 3, 4, 8) except 2, which appears once.
Example 2:
Input: single_non_duplicate([3, 3, 7, 7, 10, 11, 11])
Output: 10
Explanation: 3, 7 and 11 each appear twice; 10 is the value with no partner.
Constraints:
- 1 ≤ nums.length < 10⁵
- nums.length is odd
- -10⁵ ≤ nums[i] ≤ 10⁵
- nums is sorted in non-decreasing order
- Exactly one value appears once; every other value appears exactly twice
Hints:
O(n) is easy — XOR the whole array and the pairs cancel. The sorted order plus the O(log n) demand is a loud hint for binary search. But binary search needs a property that is false on one side of the answer and true on the other. What flips at the single element?
Look at indices. Before the single element, every pair starts at an even index: nums[0] == nums[1], nums[2] == nums[3], … After it, the pattern shifts and pairs start at odd indices. So test an even index mid: if nums[mid] == nums[mid+1], the single is to the right of the pair; otherwise it is at mid or to the left.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
Expected output: 2