540. Single Element in a Sorted Array

At a Glance

Topic: binary-search
Pattern: Binary Search (Pair invariant)
Difficulty: Medium
Companies: Google, Amazon, Meta, Apple, Adobe
Frequency: Medium
LeetCode: 540

Problem (one-liner)

Even-length sorted array where every value appears exactly twice except one value once; return that single element in O(log n) time and O(1) space.

Recognition Cues

Pairs in sorted order then one singleton
“Logarithmic time” on array with pair structure
After discarding half, remaining side still has even pair structure until singleton isolated

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — O(n) — XOR all values (works but ignores “sorted” hint) or scan pairs.
Better — O(n) — walk pairs by twos.
Optimal — O(log n) time / O(1) space — align mid to even index and compare with neighbor to see which side keeps odd pattern.

Optimal Solution

Go

func singleNonDuplicate(nums []int) int {
	left, right := 0, len(nums)-1
	for left < right {
		mid := left + (right-left)/2
		if mid%2 == 1 {
			mid--
		}
		if nums[mid] != nums[mid+1] {
			right = mid
		} else {
			left = mid + 2
		}
	}
	return nums[left]
}

JavaScript

function singleNonDuplicate(nums) {
	let left = 0;
	let right = nums.length - 1;
	while (left < right) {
		let mid = left + Math.floor((right - left) / 2);
		if (mid % 2 === 1) {
			mid--;
		}
		if (nums[mid] !== nums[mid + 1]) {
			right = mid;
		} else {
			left = mid + 2;
		}
	}
	return nums[left];
}