DSAPrep
MediumBinary Search

Find Minimum In Rotated Sorted Array

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]] 1 time 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.

Example 1

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and n times.
View original on LeetCode ↗

Linear Scan

Time O(n)Space O(1)

The minimum is the one place in the array where an element is smaller than the element before it (the rotation point). Scanning for that dip works, but it never uses the fact that both halves of the array are individually sorted, which is what makes O(log n) possible.

class Solution:
    def findMin(self, nums: list[int]) -> int:
        minimum = nums[0]
        for num in nums:
            minimum = min(minimum, num)
        return minimum

Binary Search Against the Right Endpoint

OptimalTime O(log n)Space O(1)

Compare nums[mid] to nums[hi] (the current right endpoint), not to nums[lo]. If nums[mid] > nums[hi], the rotation point — and therefore the minimum — must lie strictly to the right of mid, because a sorted run cannot have a larger value in the middle than at its own end. Otherwise, nums[mid] <= nums[hi] means the right half from mid to hi is already sorted and internally contains the minimum of that half, so the minimum is at mid or to its left, and it is safe to keep mid in play by setting hi = mid.

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
            else:
                hi = mid
        return nums[lo]

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

lo
4
0
5
1
6
2
mid
7
3
0
4
1
5
hi
2
6
lo = 0mid = 3hi = 6
1 / 4
comparingresultdiscarded

nums[mid]=7 is greater than nums[hi]=2, so the rotation point is to the right of mid. Discard indices 0 through mid and set lo = mid+1.

Why it’s correct: the array is made of at most two sorted runs; comparing nums[mid] to nums[hi] always determines which run mid belongs to and thus which side the minimum is on, without ever discarding it. Complexity: the search window halves each iteration, giving O(log n) time, O(1) space.