460. Find the Element That Appears Once in Sorted Array

Given a sorted array where every element appears exactly twice except for one element that appears only once, find and return that single element. Solve in O(log n) time and O(1) space.

Input: A sorted integer array where all elements appear twice except one.

Output: The single non-duplicate element.

Examples

Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Explanation: Before single: pairs at even indices. After: pairs shift. Binary search for misalignment.

Input: [3,3,7,7,10,11,11]
Output: 10
Explanation: 10 appears once at index 4.

Input: [1]
Output: 1
Explanation: Single element.

Constraints

• 1 <= nums.length <= 10^5
• Odd length
• All sorted
• Exactly one single element

Asked by