Java, log(n), easy solution


  • 0
    M
    
        public int search(int[] nums, int target) {
            
            if(nums.length==0)
                return -1;
            
            int index=-1;
            
            // find the pivot point
            int pivot=-1;
            for(int i=0; i<nums.length-1; i++){
                if(nums[i+1]<nums[i])
                    pivot=i+1;
            }
            if(pivot!=-1){
                index = binarysearch(nums, 0, pivot-1, target);
                if(index!=-1)
                    return index;
                index = binarysearch(nums, pivot, nums.length-1, target);
                
                return index;
            }
            
            index = binarysearch(nums, 0, nums.length-1, target);
            
            return index;
        }
        
        public int binarysearch(int[] nums, int start, int end, int target){
            while(start<=end){
                int mid = (start+end)/2;
                if(nums[mid]==target)
                    return mid;
                else if(nums[mid]<target)
                    return binarysearch(nums, mid+1, end, target);
                else
                    return binarysearch(nums, start, mid-1, target);
            }
            return -1;
        }
        
    
    

Log in to reply
 

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