QUESTION
Input 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.
“TESTCASE_1”: “9\n1 1 2 4 4 5 5 6 6\n###—###SEPERATOR—###—\nThe required element is 2”, “TESTCASE_2”: “12\n1 1 3 3 4 5 5 7 7 8 8\n###—###SEPERATOR—###—\nThe required element is 4”, “TESTCASE_3”: “11\n1 3 3 4 4 5 5 7 7 8 8\n###—###SEPERATOR—###—\nThe required element is 1”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
#include<stdio.h>
// A Binary Search based function to find the element
// that appears only once
void search(int *arr, int low, int high)
{
// Base cases
if (low > high)
return;
if (low==high)
{
printf("The required element is %d ", arr[low]);
return;
}
// Find the middle point
int mid = (low + high) / 2;
// If mid is even and element next to mid is
// same as mid, then output element lies on
// right side, else on left side
if (mid%2 == 0)
{
if (arr[mid] == arr[mid+1])
search(arr, mid+2, high);
else
search(arr, low, mid);
}
else // If mid is odd
{
if (arr[mid] == arr[mid-1])
search(arr, mid-2, high);
else
search(arr, low, mid-1);
}
}
// Driver program
int main()
{
int len,i;
scanf("%d",&len);
int arr[len];
for(i=0;i<len;i++)
scanf("%d",&arr[i]);
search(arr, 0, len-1);
return 0;
}