23. Find Minimum in Rotated Sorted Array
A sorted array of distinct values was rotated at some unknown pivot (for example [1,2,3,5,6,7] → [5,6,7,1,2,3]). Return the smallest value in O(log n).
Example 1
Input:
nums = [5,6,7,1,2,3]Output:
1Example 2
Input:
nums = [2,1]Output:
1Hint 1
Compare the middle element with the last element.
Hint 2
If nums[mid] > nums[hi], the rotation point (the minimum) is to the right.
Approach 1: Linear scan
Return min(nums).
⏱ Time O(n)💾 Space O(1)
Approach 2: Binary search on the drop ✅
Use nums[hi] to decide which half contains the rotation point.
⏱ Time O(log n)💾 Space O(1)
Reference solution for Binary search on the drop (time O(log n), space O(1)). Each solution passes every test in all four languages.
class Solution:
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is to the right of mid
else:
hi = mid # mid..hi is sorted, the minimum is at mid or left
return nums[lo]class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1; else hi = mid;
}
return nums[lo];
}
}class Solution {
public:
int findMin(vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1; else hi = mid;
}
return nums[lo];
}
};function findMin(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] > nums[hi]) lo = mid + 1; else hi = mid;
}
return nums[lo];
}Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.
This problem is explained in the lesson Binary Search.
Run your code to see results here.