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]

### Like this:

Like Loading...

*Related*