Find the Single Element in a Sorted Array

You are given a sorted array where every element appears exactly twice, except for one element which appears only once.

Your task is to find and return the element that appears only once.

You must write an efficient solution with O(log n) time complexity and O(1) space complexity.

Example

Input: [1, 1, 2, 2, 3, 4, 4]
Output: 3

Input: [1, 1, 2]
Output: 2

Input: [7]
Output: 7