Find Single Element in Sorted Array - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You are given a sorted array where every element appears exactly twice, except one element that appears only once. Your task is to find and return the single non-repeating element.

Note: The array is sorted in non-decreasing order. There will always be exactly one such unique element in the array.

If the array is empty, return null or an appropriate message indicating that the array is invalid.

Examples❯

Input Array Output Description
[1, 1, 2, 2, 3, 4, 4] 3 3 is the only number that appears once; others appear in pairs
[0, 1, 1, 2, 2, 3, 3] 0 0 is the single element at the beginning
[1, 1, 2, 2, 3, 3, 4] 4 4 is the single element at the end
[5] 5 Only one element in the array, it is the single element
[] null Array is empty, no element to return
[7, 7, 9, 9, 11, 11, 13, 15, 15] 13 13 is the only number that doesn't repeat

Solution❯

Understanding the Problem

We are given a sorted array where every element appears exactly twice, except for one element that appears only once. Our goal is to find that single, unique element.

Because the array is sorted and all duplicate elements are grouped together, we can make use of this structure to efficiently locate the single element using binary search, achieving O(log n) time complexity instead of scanning the entire array.

Step-by-Step Solution with Example

step 1: Visualize with an example

Let’s consider the array: [1, 1, 2, 2, 3, 4, 4, 5, 5]. Here, every element appears twice except for 3.

step 2: Understand pairing pattern

Normally, in a perfectly paired array like [a, a, b, b, c, c], the first of each pair is found at an even index, and its duplicate at the next (odd) index.

But once a single unique element is introduced, this pattern breaks at that point. After the unique element, all pairs shift: now the first of a pair appears at an odd index.

step 3: Use binary search

We apply binary search to find where this shift in pattern occurs. At each step:

  • We compute the mid index.
  • If mid is even and nums[mid] == nums[mid+1], it means the unique element is on the right side.
  • If mid is odd and nums[mid] == nums[mid-1], again, the unique is on the right.
  • Otherwise, the unique is on the left side (including mid).

step 4: Apply on the example

Let’s walk through the binary search on [1, 1, 2, 2, 3, 4, 4, 5, 5]:

  1. Start: low = 0, high = 8
  2. Mid = (0+8)//2 = 4 → nums[4] = 3
  3. Check neighbors: nums[3] = 2 and nums[5] = 4 → both are not equal to 3
  4. Hence, 3 is the unique element — we’ve found our answer!

step 5: Final implementation logic


def singleNonDuplicate(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if mid % 2 == 1:
            mid -= 1  # make mid even
        if nums[mid] == nums[mid + 1]:
            low = mid + 2
        else:
            high = mid
    return nums[low]

Edge Cases

  • Single element array: e.g. [7] → return 7 directly.
  • Single element at the start: e.g. [2, 3, 3, 4, 4] → 2 is unique, since it’s not equal to the next.
  • Single element at the end: e.g. [1, 1, 2] → 2 is unique, as it doesn’t match the previous.
  • Empty array: Invalid input, return null or raise an exception.

Finally

This solution is efficient and leverages the sorted structure and pairing pattern of the array. Understanding the even-odd index behavior before and after the unique element is key to narrowing the search.

Always validate the input and handle edge cases before proceeding with the binary search. If the array was unsorted or had more than one unique element, this approach wouldn’t work — a different method like XOR-based scanning would be needed.

Algorithm Steps❯

  1. Initialize start = 0 and end = n - 2.
  2. While start ≤ end:
  3. → Compute mid = start + (end - start) / 2.
  4. → Check if mid is even:
  5. → If arr[mid] == arr[mid + 1], the unique element is on the right → start = mid + 2.
  6. → Else, the unique element is on the left → end = mid.
  7. → If mid is odd:
  8. → If arr[mid] == arr[mid - 1], the unique element is on the right → start = mid + 1.
  9. → Else, the unique element is on the left → end = mid - 1.
  10. After the loop, the start index points to the single element.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int singleNonDuplicate(int arr[], int size) {
    int start = 0, end = size - 2;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if ((mid % 2 == 0 && arr[mid] == arr[mid + 1]) ||
            (mid % 2 == 1 && arr[mid] == arr[mid - 1])) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return arr[start];
}

int main() {
    int arr[] = {1, 1, 2, 2, 3, 4, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Single Element: %d\n", singleNonDuplicate(arr, size));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)If the unique element is found at the first mid index.
Average CaseO(log n)Binary search reduces the search space by half in every step.
Worst CaseO(log n)Even in the worst case, binary search checks only log(n) elements.

Space Complexity❯

O(1)

Explanation: Only a few variables (start, end, mid) are used regardless of input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...