33. 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.

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

Solution

class Solution {
    public int search(int[] nums, int target) {
                
        int lo = 0;
        int hi = nums.length - 1;
        int len = nums.length;
        if(len == 0)
            return -1;
        
        
        int findPrivotIndex = findPrivotIndex(nums);

        //try to figure out the target valus is on the left/right side of privot
        //note the elements of the privot left side are always bigger then right side
        //so we just check if the target value is smaller or bigger 
        //than the last element of right side list
        if(nums[hi] >= target){
            lo = findPrivotIndex;
        }else{
            hi = findPrivotIndex;
        }
        
        while(hi >= lo){
            int mid = lo + (hi - lo)/2;
            if(nums[mid] == target)
                return mid;
            if(nums[mid] > target){
                hi = mid - 1;
            }
            else{
                lo = mid + 1;
            }
        }
        return -1;
        
    }
    
    //find the privot/smallest index, base on this index, 
    //on both right/left side are accending sorted lists
    // notice the left side elements are always bigger than elements on right side
    //ex. 4,5,6,0,1,2,3, smallest value is 0, sperate by 0, 
    //both '4,5,6' and '1,2,3' are sorted and able use regular binary search individually 
    public int findPrivotIndex(int[] nums){
        int lo = 0;
        int hi = nums.length - 1;
        while(lo < hi){
            int mid = (lo + hi)/2;
            //make sure the nums[hi] shall be the biggest one before privot
            if(nums[mid] > nums[hi])
            {
                lo = mid + 1;
            }
            else
                hi = mid;
        }
        return lo;
    }
}