find-min-rotated.ts

/**
 * 153. Find Minimum in Rotated Sorted Array  (Medium)
 * Link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
 *
 * A sorted array of unique values was rotated at an unknown pivot. Return the
 * minimum element. Must run in O(log n).
 *
 * Example:
 *   Input:  nums = [4, 5, 6, 7, 0, 1, 2]
 *   Output: 0
 *
 * Approach:
 *   Binary search for the pivot. Compare nums[mid] with nums[hi]: if
 *   nums[mid] > nums[hi] the minimum lies strictly to the right of mid; else it
 *   is at mid or to its left. Converge until lo === hi, which is the minimum.
 *
 * Time:  O(log n)
 * Space: O(1)
 */
export function findMin(nums: number[]): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] > nums[hi]) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }

  return nums[lo];
}