Find Minimum in Rotated Sorted Array

Medium#153rotated array

A sorted array of distinct numbers was rotated: some numbers from its start moved to its end, keeping their order. Find the smallest number in O(log n) time. Our example: [15, 18, 22, 3, 6, 9, 11] — the answer is 3.

153 Find Minimum in Rotated Sorted ArrayWalkthrough · 1×

Example: [15, 18, 22, 3, 6, 9, 11]: 3..22 in order, rotated to start at 15. Each step compares nums[mid] with nums[hi].

015118222334659611lo
still in the rangerises from mid to himiddle, checked nowthrown awaythe minimum

lo starts at the first index, 0

01/16
restart · back · play · step
Speed
1function findMin(nums):
2 lo = 0
3 hi = len(nums) - 1
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 if nums[mid] > nums[hi]: // the drop is after mid
7 lo = mid + 1
8 else: // no drop: the minimum is mid or before
9 hi = mid
10 return nums[lo]
state
lo
0
hi
–
mid
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A rotated sorted array rises, drops once and rises again. The minimum is right after the drop, or at index 0 if there is no drop.
  2. Compare the middle with the right end. If nums[mid] > nums[hi], the drop is between them, so the minimum is after mid. If not, mid..hi rises with no drop, so the minimum is mid or before it.
  3. In the second case hi = mid, not mid − 1: mid may be the minimum itself. Here the very first mid lands on 3, and the range then closes on it.

Complexity

Time O(log n): every step halves the range. Memory O(1): three indices.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.