Find Minimum in Rotated Sorted Array
Binary search — compare mid to right end to decide which half holds the rotation pivot.
3 min read
binary-search array
Problem#
A sorted array has been rotated at some pivot. All values are unique. Return the minimum.
Examples#
[3,4,5,1,2]→1.[4,5,6,7,0,1,2]→0;[11,13,15,17]→11.
Constraints#
1 <= n <= 5000.
Approach#
Binary search. If nums[mid] > nums[hi], the min is in the right half; shrink lo = mid + 1. Otherwise the min is at mid or in the left half; hi = mid.
Solution#
class Solution {public: int findMin(vector<int>& nums) { int lo = 0, hi = nums.size() - 1; while (lo < hi) { int m = (lo + hi) / 2; if (nums[m] > nums[hi]) lo = m + 1; else hi = m; } return nums[lo]; }};func findMin(nums []int) int { lo, hi := 0, len(nums)-1 for lo < hi { m := (lo + hi) / 2 if nums[m] > nums[hi] { lo = m + 1 } else { hi = m } } return nums[lo]}from typing import List
class Solution: def findMin(self, nums: List[int]) -> int: lo, hi = 0, len(nums) - 1 while lo < hi: m = (lo + hi) // 2 if nums[m] > nums[hi]: lo = m + 1 else: hi = m return nums[lo]function findMin(nums) { let lo = 0, hi = nums.length - 1; while (lo < hi) { const m = (lo + hi) >> 1; if (nums[m] > nums[hi]) lo = m + 1; else hi = m; } return nums[lo];}class Solution { public int findMin(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int m = (lo + hi) >>> 1; if (nums[m] > nums[hi]) lo = m + 1; else hi = m; } return nums[lo]; }}function findMin(nums: number[]): number { let lo = 0, hi = nums.length - 1; while (lo < hi) { const m = (lo + hi) >> 1; if (nums[m] > nums[hi]) lo = m + 1; else hi = m; } return nums[lo];}Editorial#
Comparing to the right end is robust to rotation: nums[mid] > nums[hi] means the sorted part is on the right of mid, so the pivot (and minimum) is mid+1..hi. Otherwise the array from mid..hi is already sorted and mid is a candidate min.
Complexity#
- Time:
O(log n). - Space:
O(1).
Concept revision#
Related#