Find Minimum In Rotated Sorted Array#

Problem#

A sorted array of distinct integers has been rotated an unknown number of times. Find the minimum element. The array [0, 1, 2, 4, 5, 6, 7] rotated becomes something like [4, 5, 6, 7, 0, 1, 2], whose minimum is 0.

Example#

Array [4, 5, 6, 7, 0, 1, 2] returns 0. Array [3, 4, 5, 1, 2] returns 1. An unrotated array [1, 2, 3] returns 1.

Brute force#

Scan every element and track the smallest. That is O(n) and ignores the sorted structure.

Optimal approach#

The minimum is the single rotation point: the only place where an element is smaller than the one before it. Binary search for it. Compare the middle element to the rightmost element. If nums[mid] > nums[high], the rotation point (and the minimum) lies to the right of mid, so move low past mid. Otherwise the minimum is at mid or to its left, so move high to mid. When the pointers meet, they sit on the minimum.

Solution#

 1def find_min(nums: list[int]) -> int:
 2    low, high = 0, len(nums) - 1
 3    while low < high:
 4        mid = low + (high - low) // 2
 5        if nums[mid] > nums[high]:
 6            low = mid + 1
 7        else:
 8            high = mid
 9    return nums[low]
10
11
12print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0
13print(find_min([3, 4, 5, 1, 2]))        # 1
14print(find_min([1, 2, 3]))              # 1

Complexity#

• Time: O(log n).
• Space: O(1).

Pair this with search in rotated sorted array and the patterns hub. Keep going with the 60-day challenge.