Find Minimum in Rotated Sorted Array

MediumBinary SearchArrayBinary Search

Problem

An array originally sorted in ascending order, with no duplicate values, has been rotated by some unknown number of positions, so it may start partway through the original sequence and wrap around. Find the smallest value in the array.

Example. For [4, 5, 6, 7, 0, 1, 2], the minimum is 0, sitting where the sequence wraps back to the smallest values.

Key idea

Scanning the whole array works but ignores that most of it is still sorted: only one seam, where the rotation wraps around, breaks the ascending order. That seam is exactly where the minimum sits, so the problem reduces to finding it without checking every element.

Compare the value at the midpoint of the current range to the value at the range's right end. If the midpoint value is greater, the seam lies to its right, since the left portion through the midpoint is still increasing; discard the left half but keep the midpoint as a candidate. If the midpoint value is less than or equal to the rightmost value, the portion from the midpoint onward is already sorted, so the minimum is at the midpoint or to its left; discard everything to the right. Repeating this halves the range each time until the boundaries converge on the seam.

Solution

function findMin(nums: number[]): number {
  let low = 0;
  let high = nums.length - 1;

  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);

    if (nums[mid] > nums[high]) {
      // left side through mid is still increasing, so the seam is to the right
      low = mid + 1;
    } else {
      // mid or something left of it could be the seam, so keep mid in range
      high = mid;
    }
  }

  return nums[low];
}

Complexity

  • Time: O(log n). Each comparison eliminates half of the remaining range.
  • Space: O(1). Only the boundary pointers are maintained.

Watch out for

  • Compare against the rightmost element of the current range, not the leftmost; the left endpoint does not reliably indicate which side holds the seam.
  • Do not discard the midpoint when narrowing left, since it may itself be the minimum.

Pattern

This is binary search on a structure that is only piecewise sorted: instead of comparing to a fixed target, you compare adjacent boundary values to decide which half preserves the invariant you are hunting for. The same half-sorted reasoning underlies searching for an arbitrary target inside a rotated array.

Related questions