Find Minimum in Rotated Sorted Array

An array of distinct integers was sorted in increasing order and then rotated: some number of elements were moved, in order, from the front to the back. For example [1,2,3,4,5] rotated by two becomes [3,4,5,1,2]. The rotation may also be zero, leaving the array fully sorted.

Given the rotated array nums, return its smallest element. Aim for an algorithm that runs in O(log n) time.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 5000
• -5000 <= nums[i] <= 5000
• All values are distinct.
• nums is a sorted array rotated between 0 and n - 1 positions.

Pattern Path · Binary Search · problem 64 of 169

Start simple

Scan the whole array and keep the smallest value: O(n) time, O(1) space.

The key idea

The rotated array consists of two increasing runs, and every value in the left run is larger than every value in the right run. The minimum is the first element of the right run (or the first element overall when there is no rotation).

Keep a search window [lo, hi] that always contains the minimum, and compare nums[mid] with nums[hi]:

• nums[mid] > nums[hi]: the values go down somewhere between mid and hi, so mid is in the left run and the minimum lies strictly to its right. Set lo = mid + 1.
• nums[mid] < nums[hi]: the stretch from mid to hi is sorted, so nothing right of mid is smaller than it. The minimum is at mid or to its left. Set hi = mid (not mid - 1, because mid may be the answer).

The window halves every step and still contains the minimum, so when lo == hi it points at the answer. Comparing with the right end rather than the left end avoids a special case for unrotated arrays.

Complexity

• Time: O(log n)
• Space: O(1)

Python

class Solution:
    def findMin(self, nums):
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1     # the drop (and the minimum) is right of mid
            else:
                hi = mid         # mid..hi is sorted, so the minimum is at mid or left of it
        return nums[lo]

JavaScript

var findMin = function(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] > nums[hi]) lo = mid + 1;   // the drop (and the minimum) is right of mid
    else hi = mid;                            // mid..hi is sorted, so the minimum is at mid or left of it
  }
  return nums[lo];
};

What the interviewer is checking

It tests binary search on a condition rather than a key: can you find an invariant that tells you which half to discard, and get the boundary updates exactly right?

Mistakes to avoid

• Comparing with nums[lo] instead of nums[hi], which fails on arrays that are not rotated at all.
• Writing hi = mid - 1 and skipping over the minimum when it sits at mid.
• Using while lo <= hi with hi = mid, which can loop forever.
• Assuming the rotation is non-zero.

Follow-ups to expect

• What if values can repeat? (When equal, shrink hi by one; worst case O(n).)
• How do you find the rotation count? (It is the minimum's index.)
• How do you search for a target? (Pick the sorted half each step.)

In real software

Circular logs and ring buffers store sorted timestamps that wrap around; finding the oldest entry, the point where the order wraps, is this exact binary search.

Practice next