Find the element that appears only once in a sorted array

Given a sorted array where every element appears twice except for one element that appears only once, the task is to find the element that appears once. The array is sorted in ascending order.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [1, 1, 2, 3, 3, 4, 4, 8, 8]
Output: 2
Explanation: The element 2 is the only one that does not have a duplicate.

Example 2:
Input:
arr = [3, 3, 7, 7, 10, 11, 11]
Output: 10
Explanation: The element 10 is the only one that appears once.

Example 3:
Input:
arr = [5, 5, 9, 9, 12, 14, 14]
Output: 12
Explanation: The element 12 appears only once, and all other elements have duplicates.

Approach to Find the Element that Appears Once in a Sorted Array

  1. Use Binary Search:
    • The array is sorted, so a binary search can be employed to find the unique element in O(log n) time.
  2. Identify the Pattern for Pairs:
    • In a sorted array with pairs, if arr[mid] is the first element of a pair, then mid should be even; otherwise, mid should be odd. Use this pattern to adjust the search range.
  3. Adjust the Search Range:
    • If the unique element lies on the left side, update high = mid.
    • If it lies on the right side, update low = mid + 1.
    • The search continues until low == high, where the unique element is found.

C++ Program to Find the Element that Appears Once in a Sorted Array

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to find the single element in a sorted array
int singleNonDuplicate(const vector<int>& arr) {
    int low = 0, high = arr.size() - 1;

    while (low < high) {
        int mid = low + (high - low) / 2;

        // Ensure mid is even
        if (mid % 2 == 1) {
            mid--;
        }

        // Check if the unique element is on the right side
        if (arr[mid] == arr[mid + 1]) {
            low = mid + 2;
        } else {
            high = mid;
        }
    }

    return arr[low];
}

int main() {
    vector<int> arr = {1, 1, 2, 3, 3, 4, 4, 8, 8};
    cout << "The element that appears once is: " << singleNonDuplicate(arr) << endl;
    return 0;
}

Java Program to Find the Element that Appears Once in a Sorted Array

java
public class SingleElementInSortedArray {

    // Function to find the single element in a sorted array
    public static int singleNonDuplicate(int[] arr) {
        int low = 0, high = arr.length - 1;

        while (low < high) {
            int mid = low + (high - low) / 2;

            // Ensure mid is even
            if (mid % 2 == 1) {
                mid--;
            }

            // Check if the unique element is on the right side
            if (arr[mid] == arr[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        }

        return arr[low];
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 3, 3, 4, 4, 8, 8};
        System.out.println("The element that appears once is: " + singleNonDuplicate(arr));
    }
}

Python Program to Find the Element that Appears Once in a Sorted Array

python
# Function to find the single element in a sorted array
def single_non_duplicate(arr):
    low, high = 0, len(arr) - 1

    while low < high:
        mid = low + (high - low) // 2

        # Ensure mid is even
        if mid % 2 == 1:
            mid -= 1

        # Check if the unique element is on the right side
        if arr[mid] == arr[mid + 1]:
            low = mid + 2
        else:
            high = mid

    return arr[low]

# Example usage
if __name__ == "__main__":
    arr = [1, 1, 2, 3, 3, 4, 4, 8, 8]
    print("The element that appears once is:", single_non_duplicate(arr))
  • Time Complexity: O(logn) due to binary search on the array.
  • Space Complexity: O(1) as the solution uses a constant amount of extra space.

DSA

2667

507

Related Articles