public class Solution {
    public int searchRotatedArray(int[] nums, int target) {
        int peak = findPeak(nums);
        if (peak == -1)
            return binarySearch(nums, 0, nums.length - 1, target);
        if (nums[peak] == target)
            return peak;
        if (target < nums[0])
            return binarySearch(nums, peak + 1, nums.length - 1, target);
        return binarySearch(nums, 0, peak - 1, target);
    }

    public int binarySearch(int[] nums, int start, int end, int target) {
        while (start <= end) {
            int mid = (start + end) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    public int findPeak(int[] nums) {
        if (nums.length == 1)
            return 0;
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (mid < nums.length && nums[mid] > nums[mid + 1])
                return mid;
            if (mid > 0 && nums[mid] < nums[mid - 1])
                return mid - 1;
            if (nums[mid] <= nums[start]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }
}