Problem Description
Given a sorted array where every element appears exactly twice except for one element that appears only once, find and return the single element. The solution must run in O(log n) time and O(1) space.
Key Insights
- The array is sorted and identical elements appear as consecutive pairs.
- Binary search can be used to take advantage of the array's sorted property.
- Before the single element, the first occurrence of each pair is at an even index.
- After the single element, this order is disrupted, which helps in adjusting the binary search boundaries.
Space and Time Complexity
Time Complexity: O(log n) Space Complexity: O(1)
Solution
We perform a binary search on the array. At every step, we ensure that the mid index used for comparison is even by adjusting it if necessary. If the element at the even index mid is equal to the next element, it indicates that the single element is further to the right. Otherwise, the single element is to the left, including mid. This check is based on the fact that proper pairing before the single element maintains a specific even-index pattern. We continue this approach until the search space narrows down to the single element.