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])
{
if(arr[right]==arr[mid]) cout<<x<<"is haha2"<<endl;
//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
{if(arr[right]==arr[mid]) cout<<x<<"is haha3"<<endl;
//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;
}
}
}else{
// arr[first]>arr[mid], arr[mid]==arr[last]
// like 6,1,2,3,4,5,5,5,5,5,5,5,5
return search(arr,left,mid-1,x);
}
}