Smallest Element in Rotated Sorted Array

Imagine a server log whose timestamps were recorded in perfect ascending order, then someone "rotated" the file: they cut it at some line and moved the top chunk to the bottom. The values are still sorted, just split into two ascending runs that wrap around. Your job is to find the smallest value — the original first line, now hiding somewhere in the middle.

Formally: you're given an array nums that started in strictly-ascending sorted order and was then rotated at an unknown pivot. Return the minimum element. A linear scan works but is O(n); the interesting version runs in O(log n) by adapting binary search.

Signature

function arraySmallestInRotated(nums: number[]): number;
// nums is a rotated, strictly-ascending array of DISTINCT numbers.
// Returns the smallest element.

Examples

arraySmallestInRotated([4, 5, 6, 7, 0, 1, 2]);
// → 0
// The array was [0,1,2,4,5,6,7] rotated left by 4. The min, 0, now sits in the middle.

arraySmallestInRotated([1, 2, 3]);
// → 1
// Rotated zero times — still fully sorted, so the min is the first element.

Notes

• Distinct values — assume every element is unique. Arrays with duplicates are harder and need a different worst case; see Going further in the solution.
• Rotation amount — the array may be rotated anywhere from 0 to n times. A rotation of 0 (or exactly n) leaves it fully sorted.
• Not rotated returns the first element — if nums is already sorted, nums[0] is the answer.
• Single element — an array of length 1 returns that one element.
• Non-empty — you may assume nums has at least one element; you do not need to handle [].