33. Search in Rotated Sorted Array (Medium)

Description:

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.

Your algorithm’s runtime complexity must be in the order of O(log n).

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

---

Analysis:

1. Use Binary Search to find the index of the divider in the rotated array, like the following above show… (Binary Search definitely works here.)
   
2. If the index of the divider is -1, it means the length of the array is 0, we just return -1.
3. If the index of the divider is 0, it means the array is not rotated, then we use Binary Search to search the target in the whole array.
4. If the index of the division is above 0, then we continue to compare targetwith nums[0].

• If target < nums[0], the target may exist in the right part of the array.
• Else, the target may exist in the left part of the array.
• Finally, we use Binary Search to search the target in the corresponding part.

---

Code:

class Solution {
    public int search(int[] nums, int target) {
        int divider = findDivider(nums); // Try finding the index of the divider in the rotated array.
        if(divider == -1) { // The length of the array is 0, just return -1 immediately.
            return -1;
        }else {
            int res = -1;
            if(divider == 0) {  // The array is not rotated.
                res = findTarget(nums, 0, nums.length-1, target);
            }else {
                if(target < nums[0]) { // The target may exist in the right part of the array.
                    res = findTarget(nums, divider, nums.length-1, target);
                }else { // The target may exist in the left part of the array.
                    res = findTarget(nums, 0, divider-1, target);
                }
            }
            return res;
        }
    }
    
    public int findDivider(int[] nums) { // Find the index of the divider in the rotated array.
        if(nums.length == 0) {
            return -1;
        }else if(nums.length == 1) {
            return 0;
        }else {
            int left = 0, right = nums.length-1;
            if(nums[left] < nums[right]) {
                return 0;
            }else {
                int res = 0;
                while(left <= right) {
                    int mid = (left + right) / 2;
                    if(nums[mid] > nums[mid+1]) {
                        res = mid + 1;
                        break;
                    }else{
                        if(nums[mid] < nums[left]) {
                            right = mid - 1;
                        }else {
                            left = mid + 1;
                        }
                    }
                }
                return res;
            }
        }
    }
    
    public int findTarget(int[] nums, int left, int right, int target) { // Use normal binary search to find the target.
        int res = -1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                res = mid;
                break;
            }else if(nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return res;
    }
}