Loading problem...
You are given a sorted sequence of integers where every number appears exactly twice in consecutive positions, except for one unique number that appears only once.
Your task is to identify and return this lone element—the one that stands apart from all the pairs.
The challenge requires designing an algorithm that runs efficiently in O(log n) time complexity while using only O(1) auxiliary space. This constraint rules out brute-force approaches and demands a strategic search technique that leverages the sorted nature and paired structure of the input.
Think about how the position of pairs changes relative to their indices before and after the lone element appears. This structural property is key to locating the unique element efficiently.
nums = [1,1,2,3,3,4,4,8,8]2Every element appears twice (1,1), (3,3), (4,4), (8,8), except for 2 which appears only once. Hence, 2 is the lone element.
nums = [3,3,7,7,10,11,11]10The pairs are (3,3), (7,7), and (11,11). The element 10 appears alone without a pair, making it the lone element.
nums = [1,2,2,3,3]1The lone element is at the beginning of the array. The element 1 appears once, while 2 and 3 each appear twice in pairs.
Constraints