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.

Examples

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

Solution

Method 1 - Using XOR

We can use solution similar to [Single Number 1 - All elements except one occur twice](single-number-1-all-elements-except-one-occur-twice). But there array is not sorted. So, can we do better?

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)

Method 2 – Binary Search for Unique Element (Index Pairing)

Intuition

Since the array is sorted and every element appears exactly twice except for one, the unique element must disrupt the pairing pattern. Normally, pairs start at even indices (0, 2, 4, ...). If we find the first index where this pattern breaks, the single element is at or just before that position. Binary search allows us to efficiently find this point by checking the relationship between the current index and its neighbor.

Approach

1. Initialize left and right pointers for binary search.
2. While left < right:
   • Find the mid index.
   • If mid is even and nums[mid] == nums[mid + 1], the single element is to the right.
   • If mid is odd and nums[mid] == nums[mid - 1], the single element is to the right.
   • Otherwise, the single element is to the left (including mid).
3. When left == right, return nums[left] as the single element.

Complexity

• ⏰ Time complexity: O(log n), as we halve the search space each time.
• 🧺 Space complexity: O(1), since we use only a few pointers.

Code

C++

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1]) left = mid + 2;
            else right = mid;
        }
        return nums[left];
    }
};

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] {
            left = mid + 2
        } else {
            right = mid
        }
    }
    return nums[left]
}

Java

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1]) left = mid + 2;
            else right = mid;
        }
        return nums[left];
    }
}

Python

class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if mid % 2 == 1:
                mid -= 1
            if nums[mid] == nums[mid + 1]:
                left = mid + 2
            else:
                right = mid
        return nums[left]

Kotlin

class Solution {
    fun singleNonDuplicate(nums: IntArray): Int {
        var left = 0
        var right = nums.size - 1
        while (left < right) {
            var mid = left + (right - left) / 2
            if (mid % 2 == 1) mid--
            if (nums[mid] == nums[mid + 1]) left = mid + 2
            else right = mid
        }
        return nums[left]
    }
}

TypeScript

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

Rust

impl Solution {
    pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
        let (mut left, mut right) = (0, nums.len() - 1);
        while left < right {
            let mut mid = (left + right) / 2;
            if mid % 2 == 1 { mid -= 1; }
            if nums[mid] == nums[mid + 1] {
                left = mid + 2;
            } else {
                right = mid;
            }
        }
        nums[left]
    }
}