Find Minimum in Rotated Sorted Array

Examples

Input: nums = [3, 4, 5, 1, 2]
Output: 1

The original sorted order was [1, 2, 3, 4, 5]; it's been rotated so it now starts at 3.

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0

The smallest value, 0, sits partway through the list.

Input: nums = [11, 13, 15, 17]
Output: 11

This list happens not to look rotated at all, so its smallest value is simply the first element.

Constraints

• 1 <= nums.length <= 5000

• -5000 <= nums[i] <= 5000

• All the integers of nums are unique.

• nums was originally sorted in ascending order and then rotated between 1 and n times.

Approach

Scanning the whole list while tracking the smallest value seen works, but it ignores that the list is made of two sorted runs glued together.

Binary search still applies here, just with a different comparison than usual. At each step, compare the middle element to the last element of the current range. If the middle is greater than the last element, that means the rotation point — and the smallest value — must be somewhere to the right of the middle, so the middle and everything left of it can be discarded. If the middle is less than or equal to the last element, the range from the middle onward is already sorted normally, meaning the smallest value is either the middle itself or something to its left, so the right side of the range can be discarded instead. Narrowing the range this way converges on the single smallest element.

Solutions

Brute Force — Linear Scan

Walk through the whole list, keeping track of the smallest value seen so far. Correct, but ignores the sorted structure.

function findMin(nums) {
  let min = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < min) min = nums[i];
  }
  return min;
}

Time: O(n) · Space: O(1)

Optimal — Binary Search

Narrow a left/right range by comparing the middle element to the last element of the range: that comparison tells you which side the smallest value must be on.

function findMin(nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return nums[left];
}

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