Code Logo

Single Element in a Sorted Array

Published at24 Jul 2026
Created by
Medium 0 views
Like0

You are given a sorted array where every element appears exactly twice, except for one element which appears only once. Find that single element in O(log n) time. The array has an odd length and each pair consists of identical adjacent numbers.

A linear scan would check each element in O(n) time. Binary search achieves O(log n) by using index parity. Before the single element, each pair occupies two consecutive positions: index (0,1), (2,3), etc. After the single element, the pairs shift by one: (1,2), (3,4), etc.

At each step, compute the middle index. If mid is odd, decrement it to make it even. Then compare nums[mid] with nums[mid + 1]. If they are equal, the single element is to the right (lo = mid + 2). If they differ, the single element is to the left (hi = mid). This works because the pairing pattern breaks at the single element.

Edge cases include an array of length 1 (the single element is the only element), the single element at the beginning (first pair is broken), and the single element at the end.

The parity-based binary search works because the array has a consistent pairing pattern before and after the single element. Before the single element, the first element of each pair is at an even index. After, it is at an odd index. By making mid even and checking its partner, we detect which side of the single element we are on. This pattern also works for arrays with large values up to 10^5.

Example Input & Output

Example 1
Input
[3,3,7,7,10,11,11]
Output
10
Explanation

Single 10 at index 4.

Example 2
Input
[1,1,2,2,3,3,4]
Output
4
Explanation

Single at the end.

Example 3
Input
[0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8]
Output
8
Explanation

Single at the very end.

Example 4
Input
[1,1,2,3,3,4,4,8,8]
Output
2
Explanation

Single 2 at index 2 breaks pairs.

Example 5
Input
[1]
Output
1
Explanation

Single element, array length 1.

Algorithm Flow

Recommendation Algorithm Flow for Single Element in a Sorted Array

Solution Approach

Find the single element that appears only once in a sorted array where all other elements appear exactly twice. Use binary search on pairs. If mid is even and nums[mid] equals nums[mid+1], the single element is on the right. If mid is odd and nums[mid] equals nums[mid-1], the single element is also on the right. Otherwise, search left.

function singleNonDuplicate(nums) {
  var left = 0, right = nums.length - 1;
  while (left < right) {
    var 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];
}

Normalizing mid to an even index ensures we compare the first element of a pair. If pairs are intact, nums[mid] equals nums[mid+1]. A mismatch indicates the single element is in the left half.

Time complexity is O(log n), space complexity is O(1).

Best Answers

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