• # Question 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.

# Solutions

## Approach #1 - [Brute Force]

• [x] AC
• [ ] TLE

#### Intuition

Idea: what's to be said?
find the minimum in O(n)

#### Algorithm

class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return min(nums)
or
mi = max_int
for i in xrange(len(nums)):
mi = min(nums[i],mi)
return mi

## Approach #2

• [x] AC
• [ ] TLE

#### Intuition

Idea: Since O(N) is quite trivial and is not what we are expecting, we can simply use binary search in this case

suppose we have rotated array
4,5,6,7,1,2,3

L = 0, R = 6, mid = 3

we know val[mid] > val[ed] -> minimum is in [mid+1:R]

note if we have val[mid] < val[st] -> minimum is in [L:mid]

in othercases, where we have val[st] <= val[mid] <= val[ed], this is a sorted array and minium is in [L:mid]

#### Algorithm

class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
st,ed = 0,len(nums)-1
while st < ed:
mid = (st+ed)/2
#print st,ed,mid
if nums[mid] > nums[ed]:
st = mid+1
else:
ed = mid
return nums[st]

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