• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

This is a beautiful problem where binary search doesn't look for a value, but for a "Glitch" in a rhythm.

In an array where everyone has a twin, the twins should sit together in a predictable pattern:
- The 1st twin is at an EVEN index (0, 2, 4...).
- The 2nd twin is at an ODD index (1, 3, 5...).

The moment a single, lone element enters the array, it knocks everyone to its right out of sync.
- Before the lone element: Twins follow the (Even, Odd) pattern.
- After the lone element: Twins are now shoved onto (Odd, Even) indices!

Discovery: We can use Binary Search to find the exact point where this "Glitch" starts. If we are at an even index and our twin is to our right, the rhythm is still correct—the lone element must be further to the right. If the twin is NOT there, the rhythm is already broken—the lone element is at or to the left of us.

left = 0
right = length - 1

WHILE left < right:
    mid = left + (right - left) / 2
    
    // Ensure mid is always even for easy comparison
    IF mid is odd:
        mid -= 1
        
    // If the rhythm is still intact (left twin == right twin)
    IF nums[mid] == nums[mid + 1]:
        left = mid + 2 // The "glitch" is further right
    ELSE:
        right = mid // This is the glitch, or it's to the left

RETURN nums[left]

Binary Search is optimal here because the property of "being in rhythm" is binary—all elements to the left of the single one are IN rhythm, and all elements to the right are OUT of rhythm. This creates a perfect monotone transition (True, True, True, False, False, False) that binary search can exploit in O(log N).