The problem
A sorted array of distinct numbers has been rotated: some number of elements were moved from the front to the back, so [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].
Return the smallest element, in O(log n) time.
Examples
01
- Input
nums = [3, 4, 5, 1, 2]
- Output
1
02
- Input
nums = [4, 5, 6, 7, 0, 1, 2]
- Output
0
03
- Input
nums = [11, 13, 15, 17]
- Output
11
Constraints
- 1 ≤ n ≤ 5000
- −5000 ≤ nums[i] ≤ 5000
- All values are distinct; the array was sorted, then rotated 1 to n times.
The idea
The minimum sits right after the one place where the values drop. Compare the middle with the last element of the range: if nums[mid] > nums[hi], the drop is between them, so the minimum is to the right of mid.
Otherwise mid..hi is sorted, so nothing right of mid can be smaller than nums[mid]: the minimum is mid or to its left. The range shrinks to one element — the minimum.
- Time
- O(log n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def findMin(self, nums: List[int]) -> int: lo, hi = 0, len(nums) - 1 while lo < hi: mid = (lo + hi) // 2 if nums[mid] > nums[hi]: lo = mid + 1 # the drop is to the right of mid else: hi = mid # mid .. hi is sorted, so the minimum is at mid or left of it return nums[lo]