ronith
6/16/2018 - 7:49 AM

Find the element that appears once in a sorted array

Given a sorted array in which all elements appear twice (one after one) and one element appears only once. Find that element in O(log n) complexity.

Example:

Input: arr[] = {1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 8} Output: 4

Input: arr[] = {1, 1, 3, 3, 4, 4, 5, 5, 7, 7, 8} Output: 8

Find the element that appears once in a sorted array.cpp
content_copyfile_download
// https://www.geeksforgeeks.org/find-the-element-that-appears-once-in-a-sorted-array/
#include <iostream>
using namespace std;

void binary (int a[], int l, int r) {
    if (l <= r){
        if (l==r){
            cout << "The element is: "<< a[l];
            return;
        }
        int m= (l+r)/2;
        if (m%2==0){
            if (a[m] == a[m+1])
                binary(a,m+2,r);
            else
                binary(a,l,m);
        }
        else {
            if (a[m] == a[m-1])
                binary(a,m+1,r);
            else
                binary(a,l,m-1);
        }
    }
    return;
}

int main() {
    int n;
    cin>>n;
    if (n%2==0){
        cout<< "No.of elements is even, Not possible!";
        exit(0);
    }
    int a[n];
    for (int i=0;i<n;i++)
        cin>>a[i];
    cout<< "---------------- \n";
    binary(a,0,n-1);
}