Description
Return the minimum in a nonempty, rotated ascending array of distinct integers.
Solution
def find_min(nums):
left, right = 0, len(nums)-1
while left < right:
mid = (left+right)//2
if nums[mid] > nums[right]:
left = mid+1
else:
right = mid
return nums[left]Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[4,6,1,2]]- Output
1
The rotation boundary precedes 1.
Example 2
- Input
[[1,2,3]]- Output
1
The array is already sorted.
Example 3
- Input
[[7]]- Output
7
The only value is the minimum.
Approach
Compare the middle with the right endpoint to keep the half containing the minimum.
Time & space
O(log n) time; O(1) space. Here n is the input length.