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
// 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);
}