Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Solution

Explanation

The idea is to use binary search to efficiently find the minimum element in the rotated sorted array. We maintain two pointers, left and right, representing the current search range. At each step, we calculate the middle index mid and compare nums[mid] with nums[right]:

• If nums[mid] > nums[right], the minimum element must be in the right half, so we move left to mid + 1.
• Otherwise, the minimum element is in the left half (including mid), so we move right to mid.

We repeat this process until left equals right, at which point nums[left] is the minimum element.

Implementation

JavaScript

function findMinimumInRotatedSortedArray(nums) {
  let l = 0;
  let r = nums.length - 1;

  while (l < r) {
      const mid = Math.floor((l + r) / 2);

      if (nums[mid] > nums[r]) {
      l = mid + 1;
      } else {
      r = mid;
      }
  }
  return nums[l];
}

console.log(findMinimumInRotatedSortedArray([3,4,5,1,2]));
// Output: 1

Python

def find_minimum_in_rotated_sorted_array(nums):
  l, r = 0, len(nums) - 1

  while l < r:
      mid = (l + r) // 2
      if nums[mid] > nums[r]:
          l = mid + 1
      else:
          r = mid

  return nums[l]

print(find_minimum_in_rotated_sorted_array([3,4,5,1,2]))
# Output: 1

Complexity and Features

• Time Complexity: O(log n) because we are using binary search.
• Space Complexity: O(1) as we are using a constant amount of extra space.
• Features: Efficiently finds the minimum element in a rotated sorted array using binary search.