Find Minimum in Rotated Sorted Array

Share

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the rotated array, find the minimum element. All elements are unique.

Example 1
Input: [3,4,5,1,2] → Output: 1
Example 2
Input: [4,5,6,7,0,1,2] → Output: 0

Solution Approach

Binary search: if nums[mid] > nums[hi], the minimum is in the right half. Otherwise it is in the left half (including mid).

  • While lo < hi:
  • mid = lo + (hi-lo)/2.
  • If nums[mid] > nums[hi]: minimum must be in right half, lo = mid+1.
  • Else: minimum is in left half (possibly mid), hi = mid.
  • Return nums[lo].
Java
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];
    }
}
  • Time Complexity: O(log N)
  • Space Complexity: O(1)