- Identify which side of the array is unsorted from the mid
- If the target is under the sorted side of the array, find the index of the target via binary search and return the index
- If the target is under the unsorted side of the array, continue to step 1

```
public int search(int[] arr, int target) {
if(arr.length == 1 && arr[0] == target) return 0;
int low = 0, high = arr.length-1;
while(low < high) {
int mid = low + (high - low) / 2 ;
if(arr[mid] == target) { return mid; }
if(arr[low] == target) { return low; }
if(arr[high] == target) { return high; }
if(arr[mid] > arr[high] && arr[mid] > arr[low]) {
if(target < arr[mid] && target > arr[low]) {
// do binary search on left since the array on left is sorted.
return binarySearch(arr, low, mid-1, target);
}
low = mid;
}
else if(arr[mid] < arr[low] && arr[mid] < arr[high]) {
if(target > arr[mid] && target < arr[high]) {
// do binary search on right since the array on right is sorted.
return binarySearch(arr, mid+1, high, target);
}
high = mid;
}
else {
// the array is not rotated. do binary search
return binarySearch(arr, low, high, target);
}
}
return -1;
}
private int binarySearch(int[] arr, int low, int high, int target) {
while(low < high) {
int mid = low + (high - low) / 2 ;
if(arr[mid] == target) { return mid; }
if(arr[low] == target) { return low; }
if(arr[high] == target) { return high; }
if(target > arr[mid] && low != mid) low = mid;
else if (target < arr[mid] && high != mid) high = mid;
else break;
}
return -1;
}
```