Divide the array into parts using mid. There can be two possible options, either first half is sorted or second half is sorted. Then check which part the target belongs and narrow down the search.

```
int Util(int A[], int l, int r, int data)
{
if(l<=r)
{
int mid = l + (r-l)/2;
if(A[mid] == data)
return mid;
/*check if first half of the array is sorted */
if(A[l]<=A[mid])
{
/*Check whether the target belongs to this part of sub array */
if(data >=A[l] && data < A[mid])
Util(A, l, mid-1, data);
else
Util (A, mid+1, r, data);
}
/* else if the second half is sorted, repeat the same here */
else
{
if(data > A[mid] && data <= A[r])
return Util(A, mid+1, r, data);
else
return Util (A, l, mid-1, data);
}
}
else /* target not found */
return -1;
}
int search(int A[], int n, int target) {
return Util(A,0,n-1,target);
}
```