MiddleCodeCommonNot answered yet
Find the max of a rotated sorted array in O(log n)
A sorted array of distinct integers was cyclically rotated by some amount (possibly 0). Find its maximum element.
Requirements:
- O(log n) time — a variation of binary search, not a linear scan.
- Handle the not-rotated case (rotation
0).
def rotated_max(nums):
# your code hereWrite the implementation.
Binary-search for the pivot. Compare nums[mid] to nums[high]: if nums[mid] > nums[high] the peak is in the right half (low = mid + 1), else it is at mid or to its left (high = mid). The max is the element just before the rotation point — nums[low - 1] once low lands on the minimum, or simply track the larger side. O(log n); a sorted, un-rotated array returns its last element.
- ✗Falling back to an O(n) linear scan instead of binary search
- ✗Assuming the max is always at index
0or the last index - ✗Mishandling the rotation-
0case where the array is already sorted
- →Why is comparing
nums[mid]tonums[high]enough to pick the half? - →How does the approach change if duplicate values are allowed?
Contents
Task
Implement rotated_max: find the maximum of a cyclically rotated sorted array of distinct integers in O(log n).
Solution
def rotated_max(nums):
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
if nums[mid] > nums[high]: # peak is in the right half
low = mid + 1
else: # peak at mid or to its left
high = mid
# low points at the minimum; the max is the element before it
return nums[low - 1]Key points
- Comparing
nums[mid]tonums[high]decides which half holds the rotation point. lowconverges on the minimum; the max isnums[low - 1]modulo length.- A non-rotated array degenerates to plain binary search and yields the last element.
Contents
