The problem requires finding a unique element in a sorted array where every other element appears exactly twice. This specific structure helps us solve the problem efficiently using binary search.
Understanding the Structure
In a perfectly paired array (without the unique element), each pair starts at an even index: [a,a,b,b,...]. Once a single non-repeating element is inserted, it disrupts this pattern. All elements after the unique element shift by one index, and their pairing changes: one element of a pair will appear at an odd index instead of even.
Different Scenarios to Consider
- Single element in the middle: If the single element is somewhere in the middle, you'll find that the pairing breaks right after it. Using this, we can decide whether to search left or right.
- Single element at the beginning: The very first element is not equal to the one after it, so it's the answer.
- Single element at the end: The last element doesn't match the one before it — again, it's the answer.
- Single element is the only element: In case the array has only one number, it is the unique one by default.
- Empty array: Since there is no data to search, we return
null
or a custom message to indicate invalid input.
How We Approach It
We use binary search to find the single element in O(log n) time. At each step, we check whether the middle index mid
breaks the pairing pattern. Based on whether the index is even or odd, and how it compares to neighboring elements, we decide which half of the array to continue searching in.
Eventually, we narrow down the search to a single index where the unique element is located. This efficient approach is much better than a linear scan, especially for large arrays.
This method works only because the array is sorted and contains exactly one non-repeating element. If these conditions aren’t guaranteed, we’d need a different strategy.