Find Minimum in Rotated Sorted Array
Understanding the Problem
We're given an array that was originally sorted in ascending order, then rotated some number of times. A rotation takes the last element and moves it to the front. After several rotations, the array has a specific structure: there's a "pivot point" where the values drop from a large number to a small number. Everything before the pivot is part of the larger segment, and everything from the pivot onward is the smaller segment.
For example, in [4, 5, 6, 7, 0, 1, 2], the pivot is at index 4 (value 0). The array has two sorted halves: [4, 5, 6, 7] and [0, 1, 2]. The minimum is always at the pivot point.
There's one special case: if the array is rotated n times (a full rotation), it's back to the original sorted order. In that case, there's no drop, and the minimum is the first element.
So the question boils down to: where is the pivot? The element at the pivot is smaller than its predecessor and is the global minimum.
Key Constraints:
1 <= n <= 5000→ With at most 5000 elements, even O(n) would be fast. But the problem explicitly requires O(log n), so we need binary search.- All integers are unique → No duplicates. This is important because duplicates would make it impossible to always decide which half to discard. Uniqueness guarantees a clean binary search decision at every step.
numsis sorted and rotated between1andntimes → Rotatingntimes gives back the original sorted array. So we need to handle the "not actually rotated" case too.
Approach 1: Linear Scan
Intuition
Walk through the array and track the smallest element seen so far. This ignores the sorted-and-rotated structure, but it is correct and serves as a baseline before we optimize.
The minimum is either at the front (if the array completed a full rotation) or at the point where values drop. A linear scan finds it either way without reasoning about structure.
Algorithm
- Initialize
minimumto the first element of the array. - Iterate through the array from index 1 to n - 1.
- If the current element is smaller than
minimum, updateminimum. - Return
minimum.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every element in the array exactly once.
- Space Complexity: O(1). Only uses a single variable to track the minimum.
The linear scan works but ignores the sorted-and-rotated structure entirely. Since the array has two sorted halves, we can use binary search to eliminate half the search range at each step.
Approach 2: Binary Search
Intuition
A rotated sorted array is made up of two sorted subarrays, with the minimum at the boundary between them. The larger subarray comes first, followed by the smaller one. If we can decide which half holds the minimum, we discard the other half and cut the search space in half each step. That is binary search.
To decide which half to keep, compare nums[mid] with nums[right]:
- If
nums[mid] > nums[right], the minimum is somewhere aftermid. The values rise frommidand then drop before reachingright, and that drop is where the minimum sits. - If
nums[mid] <= nums[right], the minimum is atmidor to its left. The subarray frommidtorightis sorted and increasing, so the minimum is not inside it, unless it ismiditself.
Narrow the range until left == right. At that point nums[left] is the minimum.
Comparing with nums[right] rather than nums[left] is what makes the decision unambiguous. Take [3, 4, 5, 1, 2] with mid = 2 (value 5). Against nums[left] = 3, the result 5 > 3 only confirms the left portion is sorted, which says nothing about which side holds the minimum. Against nums[right] = 2, the result 5 > 2 shows the rotation point lies after mid.
The invariant is that the minimum always stays within [left, right]. When nums[mid] > nums[right], every element from left through mid belongs to the higher sorted segment, so the rotation point lies after mid. Setting left = mid + 1 excludes mid, which cannot be the minimum.
When nums[mid] <= nums[right], the subarray from mid to right is sorted and ascending. The minimum could be mid itself if mid is the rotation point, so right = mid keeps it in range. The loop ends when left == right, and since the minimum was never excluded, nums[left] is the answer. The range shrinks every iteration (left = mid + 1 strictly advances left, and right = mid strictly lowers right because mid < right whenever left < right), so termination is guaranteed.
Algorithm
- Set
left = 0andright = nums.length - 1. - While
left < right: - Compute
mid = left + (right - left) / 2. - If
nums[mid] > nums[right], the minimum is in the right half: setleft = mid + 1. - Otherwise, the minimum is at
midor in the left half: setright = mid. - Return
nums[left].
Example Walkthrough
Code
- Time Complexity: O(log n). Each iteration halves the search range. For n = 5000, that's about 13 comparisons.
- Space Complexity: O(1). Only uses a few integer variables. No recursion, no extra data structures.