Single Element in a Sorted Array
Medium · binary search
You are given a list nums of integers sorted in ascending order. Every value appears exactly twice, except for one value that appears exactly once. Equal values always sit next to each other, because the list is sorted.
Return the value that appears only once.
Examples
Example 1
Input: nums = [2, 2, 5, 5, 7, 9, 9]
Output: 7
Every value except 7 comes in a pair.
Example 2
Input: nums = [4, 6, 6]
Output: 4
The single value can be the very first item.
Example 3
Input: nums = [1, 1, 3, 3, 8]
Output: 8
It can also be the very last item.
Constraints
- 1 <= len(nums) <= 10^5
- -10^5 <= nums[i] <= 10^5
- nums is sorted in ascending order.
- Exactly one value appears once; every other value appears exactly twice. So len(nums) is odd.