Find Minimum in Rotated Sorted Array

mediumFREEBinary SearchBlind 75

Given a sorted rotated array of unique elements nums, return the minimum element.

The array was originally sorted in ascending order, then rotated between 1 and n times. You must solve it in O(log n) time.

Example

Input

3,4,5,1,2

Output

Reasoning

The input 3,4,5,1,2 is the sorted array $[1, 2, 3, 4, 5]$ rotated $3$ times: each rotation moves the last element to the front, so the final three values $3, 4, 5$ now lead.
Rotation splits the array into two ascending runs, $[3, 4, 5]$ and $[1, 2]$ . Every value in the first run is larger than every value in the second, because the first run holds the top of the original order.
The minimum is therefore the first value of the second run. It is the only position where a value is smaller than its left neighbour: $5 > 1$ is the single "drop", while $3 < 4 < 5$ and $1 < 2$ rise.
So the answer is $1$ , the original first element, which matches the output 1.
Notice that rotating $n$ times returns the array to its sorted order, as in $[11, 13, 15, 17]$ : there is no drop at all and the minimum is simply the first value, $11$ .

Constraints

1 <= len(nums) <= 5000
-5000 <= nums[i] <= 5000
All values are unique
nums was sorted then rotated

Learn this in

Patterns & MiscellaneousDSA Study Plan Binary SearchDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The problem "Find Minimum in Rotated Sorted Array" involves a binary search approach to find the minimum element in a rotated sorted array. To understand this problem, it's essential to have a solid grasp of binary search algorithms and how they can be applied to various problems. Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed the possible locations to just one.

In the context of this problem, the array was originally sorted in ascending order, then rotated between 1 and n times. This means that the array is still sorted, but the starting point of the sorted array is unknown. The rotation can be thought of as a circular shift, where the last element of the original sorted array becomes the first element of the rotated array. Understanding how this rotation affects the array's structure is crucial to developing an effective solution.

The requirement to solve this problem in O(log n) time indicates that a divide-and-conquer approach is likely necessary. This involves breaking down the problem into smaller sub-problems, solving each sub-problem, and then combining the solutions to the sub-problems to solve the original problem. In the case of binary search, this divide-and-conquer approach is used to repeatedly narrow the search space until the target element is found.

Algorithm/Approach

The general approach to solving this type of problem involves using a modified binary search algorithm. The key insight is to recognize that the rotated array can be divided into two halves, one of which is sorted. By comparing the middle element of the array to the first and last elements, we can determine which half of the array is sorted and which half might contain the minimum element. This allows us to recursively apply the binary search algorithm to the appropriate half of the array until the minimum element is found.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize two pointers, left and right, to the start and end of the array, respectively.
While left is less than right, calculate the middle index mid.
Compare the middle element nums[mid] to the first element nums[left] and the last element nums[right].
Based on the comparison, determine which half of the array is sorted and which half might contain the minimum element.
Update the left and right pointers to narrow the search space.
Repeat the process until left is no longer less than right.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Failing to handle the case where the array is not rotated (i.e., the minimum element is at the start of the array).
Incorrectly determining which half of the array is sorted.
Not updating the left and right pointers correctly.

Time & Space Complexity

The expected time complexity of the solution is O(log n), where n is the number of elements in the array. This is because the binary search algorithm divides the search space in half at each step, resulting in a logarithmic number of steps. The space complexity is O(1), as the solution only uses a constant amount of space to store the left and right pointers and the middle index mid.

solution.py

Python 3.13

Test results