Find Minimum In Rotated Sorted Array

Asked byAmazonFacebookMicrosoftAdobeGoldman SachsUber

Problem

An array sorted in ascending order has been rotated at an unknown pivot. Given the rotated array with all unique elements, find the minimum element in O(log n) time.

Examples

Example 1

Input:nums = [3,4,5,1,2]

Output:1

Example 2

Input:nums = [4,5,6,7,0,1,2]

Output:0

Constraints

1 <= nums.length <= 5000
All values in nums are unique.

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Binary Search pattern

Repeatedly halve the search space by comparing the middle element to a target, turning an O(n) scan into O(log n). It works on more than sorted arrays — any "answer space" that's monotonic (true…true…false…false) can be binary searched.

Look for this pattern when

The input is sorted, or partially sorted (like a rotated sorted array).
You're minimizing or maximizing a value where "is X feasible?" is easy to check and feasibility is monotonic.

Read the full Binary Search guide →

Video walkthroughs

Original problem on LeetCode ↗