# Leetcode: Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

Similar Problems:

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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/find-minimum-in-rotated-sorted-array
class Solution:
## Basic Ideas: Binary Search
##   Check current node with the right node of the range
##   If it's smaller, check left half(included). Check the right half(excluded)
##
##   Notice: Here we can't compare it with the left node of the range.
##      Why? (0+1)/2 == 0. We might run into dead loop with left == mid.
##
## Complexity: Time O(log(n)), Space O(1)
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
if length == 0: return None
# 4 5 6 7 0 1 2
left, right = 0, length-1
while left<right:
mid = left + (int)((right-left)/2)
if nums[mid] < nums[right]:
# check the left half(included)
right = mid
else:
# check the right half(excluded)
left = mid + 1
return nums[left]

## Basic Ideas: Binary Search
##     Find the first element, who is smaller than the first element
##     If not found, the first element is the target
##
## Complexity: Time O(log(n)), Space O(1)
def findMin_v1(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
if length == 0: return None
if length == 1: return nums[0]

if nums[0] < nums[-1]: return nums[0]
left, right = 1, length-1
# 4 5 6 7 0 1 2
while left < right:
mid = left + (int)((right-left)/2)
if nums[mid] < nums[0]:
right = mid
else:
left = mid + 1
return nums[left]

```

Share It, If You Like It.