Searching 52

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro