⚔️ Find The Lone Warrior

Binary Search on Pairs - Find the Unique Element

Steps

Target

Status

Playing

Paired Elements

Unique Warrior

Mid Pointer

Left: 0 Mid: 0 Right: 0

In an array where every element appears twice except one unique element, we can find the lone warrior using binary search!

Key Insight:

Before the unique element, pairs start at even indices: (0,1), (2,3), (4,5)...
After the unique element, pairs shift to odd indices: (5,6), (7,8)...
If mid is even, check arr[mid] == arr[mid+1]; if equal, unique is on right
If mid is odd, check arr[mid] == arr[mid-1]; if equal, unique is on right

1. Initialize left = 0, right = n-1

2. Calculate mid = left + (right - left) / 2

3. If mid is even: compare arr[mid] with arr[mid+1]

4. If mid is odd: compare arr[mid] with arr[mid-1]

5. If equal: unique is on right, so left = mid + 1

6. If not equal: unique is on left, so right = mid

7. When left == right, we found the lone warrior!