Pattern visualizer
Single Element in a Sorted Array
Scanning with XOR solves this in O(n), but the array is sorted, and sorting buys something stronger: position. Before the single element, each pair occupies an even index and the odd index after it. From the single element onward every pair is shifted by one, so pairs now START on odd indices. Force mid onto an even index and peek at its neighbour: if they match, the alignment is unbroken and the loner is further right; if they differ, the break has already happened and the loner is at mid or to its left. Half the array dies every comparison. Animated on: nums = [1,1,2,3,3,4,4,8,8] — every element appears exactly twice except one. Return that element in O(log n) time..
Binary search on pair alignment
Every value appears twice except one, so the pairs before the loner start at EVEN indices (0-1, 2-3, ...) and the pairs after it are shifted to start at ODD indices. That broken alignment is what binary search hunts for over 9 cells.
1FUNCTION singleNonDuplicate(nums)2 lo <- 03 hi <- LENGTH(nums) - 14 WHILE lo < hi5 mid <- (lo + hi) / 26 IF mid MOD 2 = 17 mid <- mid - 18 IF nums[mid] = nums[mid + 1]9 lo <- mid + 210 ELSE11 hi <- mid12 RETURN nums[lo]
← / → step · space play · Home restart