540. Single Element in a Sorted Array

Problem

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.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

Constraints:

1 <= nums.length <= 100000
0 <= nums[i] <= 100000

Problem Meaning

Given a sorted array consisting only of integers, where every element appears twice except for one number that appears only once.

Please find and return the number that appears only once.

The solution you design must satisfy O(log n) time complexity and O(1) space complexity.

Solution Approach

Suppose index idx is the single number. For even indices x to the left of idx, nums[x] == nums[x + 1],
and for odd indices y to the right of idx, nums[y] == nums[y + 1]. Based on this property, binary search can be used to find the value corresponding to idx

Code

package leetcode

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