Find Minimum in Rotated Sorted Array
Task example: Find Minimum in Rotated Sorted Array
A non-empty array nums contains distinct integers in increasing order, shifted cyclically. Return its smallest value, not its index. The array may also remain in its original sorted order after a full rotation. Keep nums unchanged. The required runtime is O(log n); the linear scan below is a baseline.
In the main example, 0 is at index 4, but the answer is 0. Values must be distinct. A single-element array is valid; an empty array is not.
Linear scan: video explanation
nums = [4, 5, 6, 7, 0, 1, 2] → 0
Prefer reading? Follow the steps below.
- Save nums[0] as smallest. Visit indices 1 through n - 1, comparing each value with the smallest value seen so far.
- Whenever nums[i] is smaller, update smallest. In [4,5,6,7,0,1,2], it starts at 4 and changes to 0 at index 4.
- Return smallest after the loop. Starting from the first element handles negative values and singleton arrays without a special initial constant.
Time complexity · O(n)
The algorithm visits all n values and makes n - 1 comparisons: O(n) time.
Space complexity · O(1)
Only smallest and the loop index are stored. The input is neither copied nor changed: O(1) extra space.
Binary search: video explanation
nums = [4, 5, 6, 7, 0, 1, 2] → 0
Prefer reading? Follow the steps below.
- Set left = 0 and right = len(nums) - 1. The minimum must stay inside this inclusive range. Continue while left < right.
- Compare nums[mid] with nums[right]. If nums[mid] is larger, the rotation point and minimum are strictly after mid, so set left = mid + 1.
- Otherwise, the minimum is at mid or before it. Set right = mid, not mid - 1. For [4,5,6,7,0,1,2], the ranges become [4,6], [4,5], then [4,4].
- When left equals right, return nums[left]. The same logic works for an already sorted array and a single element. This version relies on distinct values.
Binary search avoids scanning every value. Comparing with the right boundary identifies which half can contain the minimum; keeping mid prevents discarding the answer.
Time complexity · O(log n)
Each iteration roughly halves the candidate range, giving O(log n) time. A singleton needs no iterations.
Space complexity · O(1)
Only left, right, and mid are stored. No sorting, recursion, or copied array is needed: O(1) extra space.