Find Minimum in Rotated Sorted Array
The key idea
Compare
nums[mid] against nums[hi], not nums[lo]. If nums[mid] > nums[hi] the rotation point (and the minimum) sits strictly to the right, so move lo = mid + 1. Otherwise the minimum is at mid or to its left, so move hi = mid. The half that still contains the true minimum is always kept.Problem
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] if it was rotated 4 times, or [0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] once results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Constraints
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000- All the integers of
numsare unique numsis sorted and rotated between1andntimes
Examples
Input: nums = [3,4,5,1,2]
Output: 1
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Input: nums = [11,13,15,17]
Output: 11
Complexity
Time: O(log n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Binary Search problems
- Binary SearchEASY
- Capacity To Ship Packages Within D DaysMEDIUM
- Find First and Last Position of Element in Sorted ArrayMEDIUM
- Find in Mountain ArrayHARD
- Find K Closest ElementsMEDIUM
- Find Peak ElementMEDIUM
- First Bad VersionEASY
- Guess Number Higher or LowerEASY
- Koko Eating BananasMEDIUM
- Lowest Common Ancestor of a Binary Search TreeMEDIUM
- Median of Two Sorted ArraysHARD
- Search a 2D MatrixMEDIUM