Python solution using binary search with explanation


  • 0
    H
    class Solution(object):
        def findMin(self, nums):
    	    l = 0; r = len(nums)-1
    	    while(l<r):
    		    mid = l +(r-l)/2
    		    if (nums[mid]<nums[-1]):
    			    r = mid
    		    else:
    			    l = mid+1
    	    return nums[l]
    

    If there's a rotation, then the list consists of two increasing sequences: a1,a2,...an, then b1,b2,bn, where
    bn <a1 since bn was in front of a1 before rotation.
    So the problem could be converted to find the left most element which is smaller than the last element bn.
    This could be solved by using standard binary search techniques. The testing function is f(x) = x<bn, and is a 00001111 style problem.


Log in to reply
 

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