To solve the problem we have 4 cases to distinguish:

- A[mid] == target -> return mid
- A[start] < A[end] //i.e. both left and right halves are sorted - perform normal binary search
- right half is sorted - check if target value is between both ends of the right half; if it is - do binary search in the right half; else do binary search in the left half;
- left half is sorted - do the same as for the rigth half

```
`public int search(int[] A, int target) {`
int start = 0;
int end = A.length-1;
while(start<=end){
int mid = start + (end-start)/2;
if(A[mid] == target)
return mid;
if(A[start] < A[end]){ //both halves are sorted
if(A[mid] > target)
end = mid-1;
else
start = mid+1;
}
else if(A[mid] < A[end]){ //right half is sorted
if(A[mid] < target && target <= A[end])
start = mid+1;
else
end = mid-1;
}
else{ //left half is sorted
if(A[start] <= target && target < A[mid])
end = mid-1;
else
start = mid+1;
}
}
return -1;
}
```

Are there any better solutions?