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
Recommendation Algorithm Flow for Single Element in a Sorted Array

Solution Approach

Binary search using parity of indices. Make mid even, then compare with its partner. If equal, single is on right; else on left.

function solution(nums) {
  var lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    var mid = Math.floor((lo + hi) / 2);
    if (mid % 2 === 1) mid--;
    if (nums[mid] === nums[mid + 1]) lo = mid + 2;
    else hi = mid;
  }
  return nums[lo];
}

Time O(log n), Space 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];
    }
}