Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Solution:
Use binary search.
There exists a half which is sorted, and then we can check the sorted half if the target exists in the sorted half or not.

public class Solution {
    public int search(int[] A, int target) {
        if(A.length == 0) return -1;
        return binarySearch(A, target, 0, A.length-1);
    }
    public int binarySearch(int[] A, int target, int first, int last){
        if(last < first) return -1;
        int mid = (first + last) / 2;
        if(A[mid] == target) return mid;

        // assume left side is sorted
        if(first <= mid - 1 && A[first] <= A[mid-1]){ 
            if(target >= A[first] && target <= A[mid-1]) return binarySearch(A, target, first, mid-1);
            else return binarySearch(A, target, mid+1, last);
        }

        // otherwise right side is sorted
        else if(mid+1 <= last && A[mid+1] <= A[last]){ 
            if(target >= A[mid+1] && target <= A[last]) return binarySearch(A, target, mid+1, last);
            else return binarySearch(A, target, first, mid-1);
        }
        else return -1;
    }
}