Topic · Binary SearchMedium
Find Minimum in Rotated Sorted Array
Understand the problem
Given an array of distinct integers nums that was sorted in ascending order and then rotated at some unknown pivot. Find the minimum element in the array.
Example:
ts
nums = [3, 4, 5, 1, 2]
output = 1 // original array [1,2,3,4,5] rotated 3 steps
nums = [4, 5, 6, 7, 0, 1, 2]
output = 0 // original array [0,1,2,4,5,6,7] rotated 4 steps
nums = [11, 13, 15, 17]
output = 11 // not rotated (or rotated a full cycle)The algorithm must run in O(log n) — a linear loop is not allowed.
Basic approach
O(n) time, O(1) spacets
function findMin(nums: number[]): number {
return Math.min(...nums) // or use a linear loop
}Why this approach is slow:
Scanning the whole array for the min violates the problem's O(log n) constraint.
You need to exploit the fact that even in a rotated array, one half always keeps its sorted order, so you can cut the array in half at every step.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.