A list of different integers was sorted in increasing order and then rotated: some of its items
were moved, in order, from the end to the front. For example, [1, 2, 4, 6, 7] rotated by two
becomes [6, 7, 1, 2, 4]. It may have been rotated by any amount, including none.
Given the rotated list nums, return its smallest number in O(log n) time.
Example 1
- Input
- nums = [6, 7, 1, 2, 4]
- Output
- 1
Example 2
- Input
- nums = [11, 13, 15, 17]
- Output
- 11
Constraints
numsholds 1 to 5000 numbers, all different.- Every number is between −5000 and 5000.
numsis an increasing list rotated by some amount from 0 to n − 1.
Show the pattern
Binary search
Comparing the middle number with the last one tells you which side of the middle the break in the order (and so the minimum) is on, so you can throw away half the list at every step.
See binary search in a visualiserShow the approach
Keep a range [lo, hi] that contains the minimum, starting with the whole list. Look at mid.
If nums[mid] > nums[hi], the order breaks somewhere after mid, so the minimum is to its
right: lo = mid + 1. Otherwise nums[mid..hi] is increasing, so the minimum is mid itself
or to its left: hi = mid. When lo meets hi, it points at the minimum.
Comparing with nums[hi] rather than nums[lo] handles a list that wasn't rotated, with no
special case.
Time: O(log n) · Space: O(1)