Single Element in a Sorted Array. Find the element that appears once in a sorted array where every other element appears twice.
Given a sorted array of integers. In this array, every element appears twice except one element which appears only once. Write a code to find the element which appears only once.
For example:
Example 1:
Input: [1, 1, 2, 2, 3, 4, 4, 7, 7]
Output: 3
Except 3 every other element appears twice.
Example 2:
Input: [1, 1, 2, 2, 3, 3, 4, 5, 5]
Output: 4
NOTE – Try to solve this problem in O(logn) time complexity and by using constant space O(1).