// Function to find the pivot
int pivot_search(int A[],int low, int high)
{
if(low > high) return 1;
int mid;
mid = (low+high)/2;
if(highlow+1 == 2 && A[low] > A[high]) return low; // If there are two elements then only low and high are to be compared
if( A[mid1] < A[mid] && A[mid+1] < A[mid]) return mid;
if(A[mid] < A[low]){
return pivot_search(A,low,mid1);
} else {
return pivot_search(A,mid+1,high);
}
}
//Simple binary search
int binary(int A[], int low, int high, int x)
{
if(low > high) return 1;
int mid = (low+high)/2;
if(A[mid] == x) return mid;
if(A[mid] < x){
return binary(A,mid+1, high,x);
} else {
return binary(A,low, mid1, x);
}
}
class Solution {
public:
int search(int A[], int n, int target) {
int pivot;
pivot = pivot_search(A,0,n1);
if(pivot == 1) pivot = n1; // if pivot is not found then it means the array is sorted so pivot is n1.
// cout << pivot << endl;
if(target >= A[0]){ // if target >= A[0] then search in array till the pivot
return binary(A,0,pivot,target);
} else { // else search in the array after the pivot
return binary(A,pivot+1,n1, target);
}
}
};
My code shows correct answer on ideone on the same input but gives WA here. Ideone link : http://ideone.com/PQ1ZZl


It is running fine on two elements as well. check this link http://ideone.com/JsW1JT
The test case it fails on (as shown by LEETCODE OJ) is [5,1,3], 1.. While this test case also runs fine on ideone.