DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Find Minimum in Rotated Sorted Array

mediumBinary search

Problem statement

An ascending array of distinct integers has been rotated by an unknown amount: a block from the front was moved to the back, keeping its order. The rotation may also leave the array unchanged.

Return the smallest value in the array in O(log n) time.

Examples

Example 1

Input: nums = [40, 50, 10, 20, 30]

Output: 10

Explanation: The array was [10, 20, 30, 40, 50] rotated by three.

Example 2

Input: nums = [7, 9, 11, 13]

Output: 7

Explanation: Not rotated at all, so the minimum is the first element.

Hints

Approach

Binary-search for the drop by comparing the middle with the right end.

  1. Set lo = 0, hi = len(nums) - 1.
  2. While lo < hi:
    • mid = lo + (hi - lo) // 2;
    • if nums[mid] > nums[hi], the values wrap around somewhere after mid, so the minimum is in [mid + 1, hi]: set lo = mid + 1;
    • otherwise [mid, hi] is sorted and the minimum is at mid or to its left: set hi = mid.
  3. When lo == hi, it points at the minimum.

Comparing with nums[hi] rather than nums[lo] means the unrotated case needs no special handling.

ComplexityTime O(log n)Space O(1)
Python
class Solution:
def findMin(self, nums: list[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is to the right of mid
else:
hi = mid # mid could be the minimum
return nums[lo]

Follow-up questions

  • Return how many positions the original sorted array was rotated by.
  • Solve the same problem when duplicates are allowed.

Frequently asked questions

If nums[lo] < nums[mid], the left half is sorted, but the minimum could be nums[lo] (no rotation) or somewhere on the right. That comparison alone cannot tell the two apart. Comparing with nums[hi] always tells you which side the drop is on.

The index of the minimum is the rotation point, which is where the oldest entry sits in a wrapped ring buffer or a rotated set of log files. Many "search in a circular log" questions start by finding it.

When nums[mid] == nums[hi] you cannot tell which side the drop is on, so you shrink with hi -= 1. That keeps the answer correct, but the worst case becomes O(n), for example an array of all equal values with one smaller element.