Minimum of a rotated sorted list
A list of distinct integers was sorted from small to large and then rotated: some items were taken off the front and put on the back, keeping their order. Moving the first two items of [1, 3, 5, 7, 9] to the back gives [5, 7, 9, 1, 3]. The number of items moved can be zero, which leaves the list sorted.
You get the rotated list nums. Your function returns the smallest number in it (the value, not its index).
Reading every item gives the right answer but fails the speed test. Aim for O(log n) time, the cost of a binary search.
nums = [5, 7, 9, 1, 3]Output1The sorted list [1, 3, 5, 7, 9] had its first two items moved to the back.
nums = [8, 2, 4, 6]Output2The list drops from 8 to 2 and then climbs. The smallest sits right after the drop.
nums = [2, 4, 6, 8]Output2No items moved, so there is no drop and the first item is the smallest.
1 ≤ len(nums) ≤ 40,000,000
The values are distinct integers.
The speed test passes a list-like object with 40,000,000 items that computes each item when you read it. It supports
len(nums)andnums[i](negativeitoo) but not slicing. Reading all of its items takes seconds.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.