Leetcode/各大家 -- 33. Search in Rotated Sorted Array(Binary Search)

33. Search in Rotated Sorted Array(Binary Search)
Medium
https://leetcode.com/problems/search-in-rotated-sorted-array/

Suppose an array sorted in ascending order 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.

 LinkedIn Bloomberg Uber Facebook Microsoft

思路：* Know that rotated array is 1st reversed all, 2nd divided by 2 parts, each part do reverse order.
           So the rotated array here is in 2 parts in ascending order. [(...pivot)(pivot+1...)]
           * Use binary search to find answers in one part of the ascending subarray.
Complexity: Time O(N) Space O(1)

public class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0)return -1;
        //find pivot - nums[p] is max
        int p = 0;
        while(p < nums.length - 1){
            if(nums[p+1] >= nums[p])p++;
            else break;
        }
        if(target > nums[p]) return -1;
        if(target >= nums[0]){
            return search(nums, target, 0, p);
        }
        return search(nums, target, p + 1, nums.length - 1);
    }
    //search in sorted array
    public int search(int[] nums, int target, int start, int end){
        while(start <= end){
            int mid = start + (end - start)/2;
            if(nums[mid] == target)
                return mid;
            else if(nums[mid] <= target)
                start = mid + 1;
            else
                end = mid - 1;
        }
        return -1;
    }
}