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.
Example 1:
Input:[4, 5, 6, 7, 0, 1, 2]
Output:0
Explanation:
The minimum value in an array is 0.
Example 2:
Input:[2,1]
Output:1
Explanation:
The minimum value in an array is 1.
class Solution:
"""
@param nums: a rotated sorted array
@return: the minimum number in the array
"""
def findMin(self, nums):
# corner cases
## only one element:
if len(nums) == 1:
return nums[0]
## not rotated at all
if nums[0] < nums[-1]:
return nums[0]
# --- binary search by condition ---
# find the first element that smaller than nums[0]
# init
up = len(nums) # should satisfy
low = 0 # should not satisfy
while low + 1 < up:
mid = int((up - low)/2 + low)
if nums[mid] < nums[0]:
up = mid
else:
low = mid
# return up or low
## first after the boundary
return nums[up] # return the element, not the index
questions:
special care