Find minimum in rotated sorted array

Suppose a sorted array 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.


My Solution

I can assume that the sorted array is always ascending, and descending order is not applicable. First, we split the array into two parts: sorted part and rotated part. Thus likewise by applying binary search algorithm we can compare the mid value with the right element, if the mid value is bigger, then we can get the min value in the rotated part which is on the right side. Otherwise, the min value is in the sorted part. By iteration we will eventually get the min value as binary search will do.

def find_min(nums):
  l, r = 0, len(nums)-1
  while l < r:  # no inclusion, since we need to compare the mid value as well
    if nums[mid] > nums[r]:
      l = mid+1
    else:
      r = mid
  return nums[l]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s