← DiffPush

Find single element in sorted array

Baseline Binary Search · 1D Arrays O(log n) · O(1)

The Unpaired Beacon in a Twinned Sensor Row

A sensor row registers readings in sorted order where every model appears exactly twice - once for the primary unit and once for its standby - except one model whose standby was never commissioned. The maintenance query must find that lone model using only logarithmic probes over the sorted row.

Input: An array nums of n integers, sorted in non-decreasing order, where exactly one value appears once and every other value appears exactly twice.

Output: The value that appears exactly once.

Constraints

• 1 <= n <= 10^5
• 0 <= nums[i] <= 10^5
• n is odd
• An O(log n) algorithm with O(1) space is required

Examples

Example 1

Input: {"nums":[1,1,2,3,3,4,4,8,8]}
Output: 2
Every pairing survives until the lone 2, which breaks the alternating twos pattern.

Example 2

Input: {"nums":[3,3,7,7,10,11,11]}
Output: 10
The pairing pattern stays intact left of 10 and collapses right of it, isolating the unpaired beacon.

Solve this in your browser →

Also on LeetCode ↗