Overview

A sorted array of unique integers has been rotated between 1 and n times. Find the minimum element.

For example, [0,1,2,4,5,6,7] rotated 4 times becomes [4,5,6,7,0,1,2]. The minimum is 0.

Implement findMin(nums).

Constraints

• All values in nums are unique.
• nums is a sorted array that has been rotated 1 to n times.
• nums always has at least one element.
• Must achieve $O(\log n)$ time complexity.

Examples

findMin([3, 4, 5, 1, 2]);        // 1
findMin([4, 5, 6, 7, 0, 1, 2]);  // 0
findMin([11, 13, 15, 17]);       // 11 — no effective rotation
findMin([2, 1]);                  // 1

Notes

• Binary search variant: compare the mid element with the rightmost element. If nums[mid] > nums[hi], the minimum is in the right half; otherwise it's in the left half (including mid).
• If the array isn't actually rotated (already sorted), the first element is the minimum — the binary search handles this naturally.
• Unlike the standard rotated search, you don't need a target — you're always converging on the inflection point.

Solution

function findMin(nums) {
  let lo = 0, hi = nums.length - 1;

  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (nums[mid] > nums[hi]) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }

  return nums[lo];
}

Resources

• Find Minimum in Rotated Sorted Array — LeetCode
• Binary Search — Wikipedia