A not-so-intuitive and recursive solution, yet faster! ?


  • 0
    L

    This is my first solution. Instead of comparing the boundaries, the algorithm compares its neighbours. Therefore, in the case of that the neighborhood follows the sorted order, it has to (recursively) check both its ends.
    However, it runs faster by OJ. My guess is that the early returns pay off.

    {

    public int findMin(int[] num) {
    	int start = 0, end = num.length-1;
    	return findMin_rec(num, start, end);
    }
    
    public int findMin_rec(int[] num, int start, int end) {
    	
    	if(num.length == 1){
    		return num[0];
    	}
    	
    	int mid = 0;
    	while(start < end){
    		mid = (start+end)/2;
    		
    		if(mid==0){
    			return Math.min(num[0], num[1]);
    		}
    		
    		if(num[mid-1] < num[mid] && num[mid] > num[mid+1]){
    			return num[mid+1];
    		}else if(num[mid-1] > num[mid] && num[mid] < num[mid+1]){
    			return num[mid];
    		}else if(num[mid-1] < num[mid] && num[mid] < num[mid+1]){
    			return Math.min(findMin_rec(num, start, mid-1), 
    						    findMin_rec(num, mid+1, end));
    		}
    	}
    	
    	return num[start];
    }
    

    }


Log in to reply
 

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