← DiffPush

Find the minimum element in sorted rotated array

Baseline Binary Search · 1D Arrays O(log n) · O(1)

Finding the Restart Point of a Wrapped Shift Schedule

A control room stores a duty roster of unique shift codes that was written in ascending order and later wrapped around the display. The smallest code marks where the wrap begins, and the dispatcher needs it to rebuild the schedule. Locate that minimum in a logarithmic number of probes.

Input: An array nums of n unique integers, sorted ascending and then rotated between 1 and n times.

Output: The minimum element of nums.

Constraints

• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All values in nums are unique

Examples

Example 1

Input: {"nums":[4,5,6,7,0,1,2]}
Output: 0
The wrap begins right after 7, so the smallest code 0 sits at the restart point.

Example 2

Input: {"nums":[3,4,5,1,2]}
Output: 1
The descending junction sits between 5 and 1, and the probe logic converges on 1.

Solve this in your browser →

Also on LeetCode ↗