Course4all

Single Element in a Sorted Array

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once. Your solution must run in O(logN)O(\\log N) time and O(1)O(1) space.
Medium

Examples

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
Input: nums = [3,3,7,7,10,11,11]
Output: 10
Approach 1

Level I: XOR Manipulation

Intuition

XORing a number with itself results in 0. XORing 0 with any number results in that number. If we XOR all elements, the pairs will cancel out, leaving the single element.
⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [1,1,2] 1 ^ 1 ^ 2 = 0 ^ 2 = 2. Result: 2.
java
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int res = 0;
        for (int n : nums) res ^= n;
        return res;
    }
}
Approach 2

Level II: Linear Scan (Pairs)

Intuition

Since the array is sorted, we can check elements in pairs. If nums[i] is not equal to nums[i+1], then nums[i] is the single element.
⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [1,1,2,3,3]
  • i=0: nums[0]==nums[1] (1==1). Continue.
  • i=2: nums[2]!=nums[3] (2!=3). Return nums[2]=2.
java
class Solution {
    public int singleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return nums[nums.length - 1];
    }
}
Approach 3

Level III: Optimal (Binary Search on Even Indices)

Intuition

In a paired array, pairs start at even indices: (0,1), (2,3), etc. Before the single element, nums[even] == nums[even+1]. After the single element, this pattern breaks. We search for the first index where nums[even] != nums[even+1].
⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

StepLRMidMid_Evennums[M_E] == nums[M_E+1]Decision
108443 == 4 (No)R = 4
204222 == 3 (No)R = 2
Exit22---Return nums[2] = 2
java
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1]) l = mid + 2;
            else r = mid;
        }
        return nums[l];
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSearch a 2D Matrix
Next Question →Find K Closest Elements