A sorted (ascending) array of distinct values has been rotated at some unknown pivot
(e.g. [3, 4, 5, 1, 2]). Return its minimum value in O(log n).
minRotated(nums)
Input format: space-separated integers (non-empty).
[3, 4, 5, 1, 2] // → 1
[4, 5, 6, 7, 0, 1, 2] // → 0
[11, 13, 15, 17] // → 11 (not rotated)
A rotated sorted array isn't sorted end-to-end, so ordinary binary search seems broken — there's no single target yet, and the array isn't monotonic. But look closer: a rotation is two sorted runs glued together, with the second run's values all smaller than the first's. There's exactly one point where a value is smaller than the one before it — the rotation point, and the minimum.
Even though the raw values aren't monotonic, you can build a monotonic condition: pick the last element as a reference, and ask "is nums[i] > nums[last]?" Every index in the first (higher) run answers true; every index in the second (lower) run, including the last element, answers false. True for a prefix, false for the rest — monotonic, despite the values going up then jumping down.
Compare the middle to the right boundary instead of a fixed target. If the middle is greater, it's still in the first run, so the rotation point is to the right — discard the middle and everything left. If the middle is less than or equal, it's already in the second run, so the minimum is at the middle or to its left — discard everything right of the middle, keeping the middle as a candidate.
The range always contains the true rotation point and shrinks by half each comparison, until the boundaries converge.
A linear scan checking each element against its neighbor takes time proportional to the array's length in the worst case. Exploiting the monotonic "greater than the rightmost" condition locates the rotation point in logarithmic time — the same advantage binary search always has, applied to a cleverly chosen condition instead of a direct value comparison.
def min_rotated(nums):
lo = 0
hi = len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.