Python binary search O(log(n))


  • 0
    A

    Applying binary search to find the rotation point mid where nums[mid] > nums[mid+1].
    If nums[lo] > nums[mid] then the rotation point is in [lo, mid) else (mid, hi].

    class Solution(object):
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n = len(nums) - 1
            lo = 0
            hi = n
            while hi >= lo:
                mid = lo + ((hi-lo)>>1)
                if mid < n and nums[mid] > nums[mid + 1]:
                    #Rotation point
                    return nums[mid + 1]
                if nums[lo] > nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            # No rotation has been performed
            return nums[0] 
    

Log in to reply
 

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