Problem Description
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Return the single element that appears only once. Your solution must run in O(log n) time and O(1) space.
Key Insights
- The array is sorted, which allows the use of a binary search approach.
- Every element that appears twice will have its first occurrence at an even index and its second occurrence at an odd index.
- When the unique element is encountered, the pattern of even and odd indices will be disrupted.
- We can leverage the properties of indices to narrow down the search space.
Space and Time Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Solution
To solve this problem, we will use a binary search algorithm. The key idea is to use the properties of sorted arrays and the index of elements to identify the single element. We will maintain two pointers, left and right, to represent the current search space. At each step, we will calculate the middle index and check the relationship of the middle element with its neighbors. Depending on whether the middle index is even or odd and how it relates to its neighbors, we will adjust the search space accordingly. This approach ensures that we only look at a logarithmic number of elements, achieving the desired time complexity.