153. Find Minimum in Rotated Sorted Array

Link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array

Description: Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Find the minimum element in the array.

Solution:

We can use binary search to find the minimum element in the rotated sorted array. We can start with the left and right pointers at the beginning and end of the array. We can find the mid element and check if the mid element is greater than the right element. If the mid element is greater than the right element, we can move the left pointer to the right of the mid element. If the mid element is less than or equal to the right element, we can move the right pointer to the mid element. We can continue this process until the left pointer is less than the right pointer. The left pointer will be at the minimum element in the rotated sorted array.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    const m = left + Math.floor((right - left) / 2)

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

  return nums[left]
}