Simple java solution - find the pivot locations first


  • 0

    '''

    public int search(int[] nums, int target) {
        
        if(nums.length == 0) return -1;
        if(nums[0] < nums[nums.length - 1]) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }
        
        int lo = 0, hi = nums.length - 1;
        int mid, pleft, pright;
        
        while(lo < hi - 1) {
            mid = (lo + hi) /2;
            if(nums[mid] > nums[0]) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        
        if(target >= nums[0]) { 
            return binarySearch(nums, target, 0, lo);
        }
        else {
            return binarySearch(nums, target, hi, nums.length - 1);
        }
        
    }
    
    public int binarySearch(int[] nums, int target, int lo, int hi) {
        
        int mid;
        while(lo <= hi) {
            mid = (lo + hi) / 2;
            if(target < nums[mid]){
                hi = mid - 1;
            } else if(target > nums[mid]) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }
        
        return -1;
    }
    

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.