The most satisfying First True problem. The condition is a parity trick — and once you see it, the whole solution clicks in seconds.
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Return the single element that appears only once. Your solution must run in O(log n) time and O(1) space.
This problem feels like it needs XOR or a clever scan — until you notice the parity structure hidden inside the sorted array.
Before the single element, every pair occupies an even-odd pair of indices. After the single element, the pairs shift to odd-even. This shift is the F→T boundary we binary search.
Before the single element, if mid is even, its pair is at mid+1. After the single element, if mid is even, its pair is at mid-1. Detecting which side the pair is on tells us which side of the boundary we're on.
The condition that creates our F→T boundary is:
At an even index before the single element: nums[mid] == nums[mid+1] (the pair is ahead) → FALSE
At an even index at or after the single element: nums[mid] != nums[mid+1] (pair shifted behind) → TRUE
Handling odd mid: We only want to evaluate even indices. If mid is odd, shift it down by 1 (mid-- or mid &= ~1 i.e. round down to even). This keeps the parity logic consistent.
Array: [1, 1, 2, 3, 3, 4, 4, 8, 8]
3 != 4? Yes → condition TRUE. Save boundary=4, search left: right=3.
1 != 1? No → condition FALSE. Search right: left=1+1=2. (We search right of the unadjusted mid+1)
2 != 3? Yes → condition TRUE. Save boundary=2, search left: right=1.
Return nums[boundary] = nums[2] = 2. Correct!
class Solution { public int singleNonDuplicate(int[] nums) { int left = 0; int right = nums.length - 1; int boundary = 0; while (left <= right) { int mid = left + (right - left) / 2; // Always evaluate at an even index for consistent parity logic if (mid % 2 == 1) mid--; if (nums[mid] != nums[mid + 1]) { // Pair has shifted — single element is here or to the left boundary = mid; right = mid - 1; } else { // Pair is intact — single element is to the right left = mid + 2; // skip over the intact pair } } return nums[boundary]; } }
class Solution: def singleNonDuplicate(self, nums: list[int]) -> int: left, right = 0, len(nums) - 1 boundary = 0 while left <= right: mid = left + (right - left) // 2 # Always evaluate at an even index for consistent parity logic if mid % 2 == 1: mid -= 1 if nums[mid] != nums[mid + 1]: # Pair has shifted — single element is here or to the left boundary = mid right = mid - 1 else: # Pair is intact — single element is to the right left = mid + 2 # skip over the intact pair return nums[boundary]
Why left = mid + 2? When the pair is intact at mid and mid+1, we know both elements are accounted for and neither is the single element. We can safely skip both by jumping to mid + 2 rather than just mid + 1.