Find Minimum in Rotated Sorted Array
Binary search using the sorted half as a compass
A rotated sorted array splits into exactly two sorted runs, and the minimum sits right at the seam between them. At any midpoint, comparing it to the rightmost element reveals which half is the fully-sorted one — the seam can never be inside a sorted half, so it's always safe to discard that half and keep searching the other.
Details
Animated on: nums = [4,5,6,7,0,1,2] — a sorted array rotated at an unknown pivot. Find the minimum in O(log n).
Problem:Find Minimum in Rotated Sorted ArrayMedium
Pattern:Binary Search on Sorted Data
Binary search using the sorted half as a compass
step 1 / 8
nums=[4,5,6,7,0,1,2] is sorted then rotated. Binary search: whichever half is NOT sorted still contains the rotation point (the minimum).
- low=0· arr[0] = 4
- high=6· arr[6] = 2
1FUNCTION findMin(nums):2 set low to 0, high to (length of nums) - 13 WHILE low < high:4 mid = midpoint of low and high, rounded down5 IF nums[mid] > nums[high]:6 low = mid + 1 (seam is to the right)7 ELSE:8 high = mid (seam is at mid or to the left)9 RETURN nums[low]
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- nums=[4,5,6,7,0,1,2] is sorted then rotated. Binary search: whichever half is NOT sorted still contains the rotation point (the minimum).
- mid=3 -> value 7. Compare against nums[high]=2.
- 7 > 2: the left half (low..mid) is fully sorted and can't contain the minimum — it must be to the right. low = mid+1 = 4.
- mid=5 -> value 1. Compare against nums[high]=2.
- 1 <= 2: the right half (mid..high) is sorted, so the minimum is at mid or to its left. high = mid = 5.
- mid=4 -> value 0. Compare against nums[high]=1.
- 0 <= 1: the right half (mid..high) is sorted, so the minimum is at mid or to its left. high = mid = 4.
- low and high converged at index 4. Minimum value = 0.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.