Find Minimum in Rotated Sorted Array (#153)

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. You may assume no duplicate exists in the array.

Example

Example 1

Input: [3, 4, 5, 1, 2]
Output: 1

Example 2

Input: [4, 5, 6, 7, 0, 1, 2]
Output: 0

Solution

Solution I (Reference)

Observation

If the sorted array is not rotated, the last element always larger than first element.

[2, 3, 4, 5, 6, 7]
 ^              ^

However, if the sorted array is rotated, we want to find the Infection Point (i.e. the point whose left element is maximum and right element is minimum).

[4, 5, 6, 7, 2, 3]
           ^

Furthermore,

• All the elements to the left of inflection point > first element of the array.
• All the elements to the right of inflection point < first element of the array.

Algorithm

[5, 1, 2, 4, 5]
 l     m     r
 <-----

[5, 1, 2, 4, 5]
 l  r
 m

[4, 5, 6, 7, 2, 3]
 l     m        r
         ------->

[4, 5, 6, 7, 2, 3]
          l  m  r

Time Complexity:\(O(log\,n)\), Space Complexity:\(O(1)\)

Code

class Solution:
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if len(nums) == 1:
            return nums[0]


        l, h = 0, len(nums) - 1

        if nums[h] > nums[l]:
            return nums[l]

        while l <= h:
            m = l + (h - l) // 2
            if nums[m] > nums[m + 1]:
                return nums[m + 1]
            if nums[m - 1] > nums[m]:
                return nums[m]

            if nums[m] > nums[0]:
                l = m + 1
            else:
                h = m - 1