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.

Example

Array              Target    Result
[4, 5, 1, 2, 3]    4         0
[4, 5, 1, 2, 3]    1         2
[4, 5, 1, 2, 3]    0         1
public class Solution {
    /** 
     *@param A : an integer rotated sorted array
     *@param target :  an integer to be searched
     *return : an integer
     */
    public int search(int[] A, int target) {
        if(A == null || A.length == 0)
            return -1;
        
        int cut = searchPivot(A);
        
        //If cut == -1, then there is not cut -> array is sorted.
        //Just perform binary search.
        if(cut == -1)
        {
            int search = Arrays.binarySearch(A, target);
            if(search < 0)
                return -1;
            else
                return search;
        }
        
        //Perform binary search on the portion of the array before the cut
        //binarySearch(A, start inclusive, end exclusive, target)
        int search = Arrays.binarySearch(A, 0, cut, target); 
        //If found just return
        if(search >= 0)
            return search;
        
        //Search again on the portion after cut.
        search = Arrays.binarySearch(A, cut, A.length, target);
        if(search >= 0)
            return search;
        return -1;
    }
    
    /**
     * Gets the index of the first out of order (non-ascending) element.
     * @return -1 if not found.
     */
    static int searchPivot(int[] a)
    {
        for(int i = 0; i < a.length; i++)
        {
            if(i == 0)
                continue;
            if(a[i] < a[i -1])
                return i;
        }
        return -1;
    }
}