lc-33

//There is an integer array nums sorted in ascending order (with distinct values
//). 
//
// Prior to being passed to your function, nums is possibly rotated at an unknow
//n pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k]
//, nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For 
//example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0
//,1,2]. 
//
// Given the array nums after the possible rotation and an integer target, retur
//n the index of target if it is in nums, or -1 if it is not in nums. 
//
// You must write an algorithm with O(log n) runtime complexity. 
//
// 
// Example 1: 
// Input: nums = [4,5,6,7,0,1,2], target = 0
//Output: 4
// Example 2: 
// Input: nums = [4,5,6,7,0,1,2], target = 3
//Output: -1
// Example 3: 
// Input: nums = [1], target = 0
//Output: -1
// 
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 5000 
// -104 <= nums[i] <= 104 
// All values of nums are unique. 
// nums is an ascending array that is possibly rotated. 
// -104 <= target <= 104 
// 
// Related Topics Array Binary Search 
// 👍 15303 👎 957


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int search(int[] nums, int target) {
        if (nums[0] < nums[nums.length - 1]) {
            return searchInner(nums, target, 0, nums.length - 1, true);
        } else {
            return searchInner(nums, target, 0, nums.length - 1, false);
        }
    }

    private int searchInner(int[] nums, int target, int from, int end, boolean isAsc) {
        if (from == end) {
            if (nums[from] == target) {
                return from;
            } else {
                return -1;
            }
        }

        if (from + 1 == end) {
            if (nums[from] == target) {
                return from;
            } else if (nums[end] == target) {
                return end;
            } else {
                return -1;
            }
        }

        int mid = from + (end - from) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        if (isAsc) {
            if (nums[mid] < target) {
                return searchInner(nums, target, mid, end, true);
            } else {
                return searchInner(nums, target, from, mid, true);
            }
        } else {
            if (nums[mid] <= nums[from] && nums[mid] <= nums[end]) {
                if (nums[mid] < target) {
                    if (nums[end] < target) {
                        return searchInner(nums, target, from, mid, false);
                    } else {
                        return searchInner(nums, target, mid, end, true);
                    }
                } else {
                    return searchInner(nums, target, from, mid, false);
                }
            } else {
                if (nums[mid] > target) {
                    if (nums[end] < target) {
                        return searchInner(nums, target, from, mid, true);
                    } else {
                        return searchInner(nums, target, mid, end, false);
                    }
                } else {
                    return searchInner(nums, target, mid, end, false);
                }
            }
        }

    }
}
//leetcode submit region end(Prohibit modification and deletion)