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]
}