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