#include<iostream>
#include<cstdio>
using namespace std;
int search(int arr[],int left, int right, int x)
{
if(left > right)
return -1;
int mid=left+(right-left)/2;
//X FOUND AT MID INDEX
if(arr[mid]==x)
return mid;
//IF LEFT MOST ELEMENT IS LESS THAN MID ELEMENT
if(arr[left] < arr[mid])
{
//CHECK IF X LIES IN THE RANGE OF LEFT TO MID ELEMNTS
if((arr[left] <= x) && (x <= arr[mid]))
{
//IF YES THEN SEARCH IN THE RANGE OF LEFT TO MID-1 ELEMNTS
return search(arr,left,mid-1,x);
}
else
{
//IF NO THEN SEARCH IN THE RANGE OF MID+1 TO RIGHT ELEMNTS
return search(arr,mid+1,right,x);
}
}
//IF MID ELEMENT IS LESS THAN RIGHT MOST ELEMENT
else if(arr[mid] < arr[right])
{
//CHECK IF X LIES IN THE RANGE OF MID TO RIGHT MOST ELEMNTS
if((arr[mid] <= x) && (x <= arr[right]))
{
//IF YES THEN SEARCH IN THE RANGE OF MID+1 TO RIGHT ELEMNTS
return search(arr,mid+1,right,x);
}
else
{
//IF NO THEN SEARCH IN THE RANGE OF LEFT TO MID-1 ELEMNTS
return search(arr,left,mid-1,x);
}
}
//CHECK IF LEFT MOST ELEMENT TO MID ELEMENT ARE ALL REPEATS
else if(arr[left] == arr[mid])
{
//IF YES THEN CHECK MID ELEMENT AND RIGHT MOST ELEMENT ARE SAME OR NOT
if(arr[mid] != arr[right])
{
//IF MID ELEMENT AND RIGHT MOST ELEMENT ARE NOT SAME
//THEN SEARCH IN RANGE OF MID+1 TO RIGHT ELEMNTS
return search(arr,mid+1,right,x);
}
//IF NO THEN SEARCH HAS TO BE DONE IN BOTH HALVES
else
{
//FIRST SEARCH IN THE FIRST HALF
int result=search(arr,left,mid-1,x);
//NOT FOUND A MATCH
if(result == -1)
{
//SO SEARCH IN THE SECOND HALF
return search(arr,mid+1,right,x);
}
//FOUND A MATCH
else
{
//RETURN THE RESULT INDEX
return result;
}
}
}
//DIDN'T FIND THE ELEMENT AT ALL
return -1;
}
int main()
{
// LET US SEARCH 3 IN BELOW ARRAY
int arr1[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
int arr_size = sizeof(arr1)/sizeof(arr1[0]);
int no = 3;
printf("Index of the element is %d\n", search(arr1,0,arr_size-1,no));
// LET US SEARCH 3 IN BELOW ARRAY
int arr2[] = {3, 4, 5, 1, 2};
arr_size = sizeof(arr2)/sizeof(arr2[0]);
printf("Index of the element is %d\n", search(arr2,0,arr_size-1,no));
// LET US SEARCH FOR 4 IN ABOVE ARRAY
no = 4;
printf("Index of the element is %d\n", search(arr2,0,arr_size-1,no));
// LET US SEARCH 0 IN BELOW ARRAY
int arr3[] = {1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1};
no = 0;
arr_size = sizeof(arr3)/sizeof(arr3[0]);
printf("Index of the element is %d\n", search(arr3,0,arr_size-1,no));
// LET US SEARCH 3 IN BELOW ARRAY
int arr4[] = {2, 3, 0, 2, 2, 2, 2, 2, 2, 2};
no = 3;
arr_size = sizeof(arr4)/sizeof(arr4[0]);
printf("Index of the element is %d\n", search(arr4,0,arr_size-1,no));
// LET US SEARCH 2 IN ABOVE ARRAY
no = 2;
printf("Index of the element is %d\n", search(arr4,0,arr_size-1,no));
// LET US SEARCH 3 IN BELOW ARRAY
int arr5[] = {1, 2, 3, 4};
no = 3;
arr_size = sizeof(arr5)/sizeof(arr5[0]);
printf("Index of the element is %d\n", search(arr5,0,arr_size-1,no));
return 0;
}