Single Element in a Sorted Array

Given a sorted array consisting of only integers where every element appears exactly twice except for one element which appears exactly once, find this single element.

Your solution must run in O(log n) time and O(1) space.

Examples

Example 1:

Input: nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]

Output: 2

Example 2:

Input: nums = [3, 3, 7, 7, 10, 11, 11]

Output: 10

Constraints

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• Every element appears exactly twice except for one element which appears once