AlgoMaster Logo

Find Minimum in Rotated Sorted Array

Last Updated: March 29, 2026

medium
4 min read

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 simply 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.
  • nums is sorted and rotated between 1 and n times → Rotating n times gives back the original sorted array. So we need to handle the "not actually rotated" case too.

Approach 1: Linear Scan

Intuition

The simplest approach: just walk through the array and track the smallest element. This doesn't use any information about the sorted-and-rotated structure, but it's correct and easy to reason about.

Since the array was originally sorted and then rotated, the minimum will either be at the very beginning (if the array completed a full rotation) or at the point where the values suddenly drop. But we don't even need to think about that for a linear scan. Just check every element and keep track of the smallest one.

Algorithm

  1. Initialize minimum to the first element of the array.
  2. Iterate through the array from index 1 to n - 1.
  3. If the current element is smaller than minimum, update minimum.
  4. Return minimum.

Example Walkthrough

1Initialize: minimum = nums[0] = 3, start scanning from i=1
0
3
min=3
1
4
i
2
5
3
1
4
2
1/4

Code

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

Here's the key insight about a rotated sorted array: it's made up of two sorted subarrays, and the minimum sits at the boundary between them. The larger sorted subarray comes first, followed by the smaller one. If we can figure out which half of the array the minimum is in, we can discard the other half, cutting our search space in half each time. That's binary search.

But how do we decide which half to keep? The trick is to compare nums[mid] with nums[right]:

  • If nums[mid] > nums[right], the minimum must be somewhere to the right of mid. Why? Because the values go up from mid and then must drop at some point before reaching right. The drop is where the minimum lives.
  • If nums[mid] <= nums[right], the minimum is at mid or to the left of mid. The subarray from mid to right is already sorted and increasing, so the minimum can't be hiding in there (unless it's mid itself).

We keep narrowing the search range until left == right, and at that point, nums[left] is the minimum.

Why compare with nums[right] instead of nums[left]? Consider [3, 4, 5, 1, 2] with mid = 2 (value 5). Comparing with nums[left] = 3, we see 5 > 3, which just tells us the left portion is sorted. But that doesn't tell us which side has the minimum. Comparing with nums[right] = 2, we see 5 > 2, which clearly tells us the rotation point (and thus the minimum) is to the right of mid.

Algorithm

  1. Set left = 0 and right = nums.length - 1.
  2. While left < right:
    • Compute mid = left + (right - left) / 2.
    • If nums[mid] > nums[right], the minimum is in the right half: set left = mid + 1.
    • Otherwise, the minimum is at mid or in the left half: set right = mid.
  3. Return nums[left].

Example Walkthrough

1Initialize: left=0, right=4, search range = entire array
0
3
left
1
4
2
5
3
1
4
2
search range
1/6

Code