Find Minimum in Rotated Sorted Array

The "Find Minimum in Rotated Sorted Array" problem is an intriguing search problem that involves finding the minimum element in a sorted array that has been rotated at some unknown pivot point.

Problem Statement

Given a rotated sorted array, the goal is to find the minimum element. The original array is sorted in ascending order but then rotated at some pivot.

Examples

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

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.

Constraints

• 1 <= nums.length <= 5000
• -5000 <= nums[i] <= 5000
• The array is sorted and rotated at some pivot.

Binary Search Solution

The solution leverages a modified binary search due to the sorted nature of the array:

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

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

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

  return nums[left];
}

Explanation

• The algorithm initiates a binary search. However, instead of searching for a specific value, it looks for the inflection point.
• The inflection point is where we find the smallest element.
• The logic in the binary search is modified to find this point by comparing the middle element with the rightmost element to decide which half of the array to continue the search.

This problem is a classic example used in interviews to assess a candidate's proficiency in modifying and applying binary search in different scenarios.