Description
Given a sorted array where every element appears twice except one, find the single element in O(log n) time.
Examples
Input:
nums = [1,1,2,3,3,4,4,8,8]Output:
2Explanation:
2 appears once.
Input:
nums = [5]Output:
5Explanation:
In the minimal case with only one element, that element appears once and is the answer.
Input:
nums = [2,2,9,9,15,22,22,25,25]Output:
15Explanation:
15 appears once while all other elements (2, 9, 22, 25) appear exactly twice each.
Constraints
- •
1 ≤ nums.length ≤ 10⁵