Find Minimum in Rotated Sorted Array

MediumBinary Searchrotated-array-min

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] could become:

[3,4,5,6,1,2] if it was rotated 4 times [1,2,3,4,5,6] if it was rotated 6 times

Notice that rotating an array 4 times moves the last four elements of the array to the beginning. Rotating an array 6 times returns the original array.

Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.

A solution that runs in O(n) time is trivial. Can you write an algorithm that runs in O(log n) time?

Example 1:

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original array was [1,2,3,4,5] and it was rotated 3 times.

Example 2:

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Recommended time and space complexity

You should aim for a solution with O(log n) time complexity and O(1) space complexity, where n is the size of the input array.


Hint 1

Linear search (O(n)) is simple, but can you use the fact that the array was originally sorted? Think about binary search.


Hint 2

The array is divided into two sorted parts. The minimum element is at the boundary of these parts. How can you find this boundary?


Hint 3

In binary search, compare the middle element with the right end. This will help determine which part contains the minimum.

This problem tests understanding of binary search and its application to modified sorted arrays. It helps develop skills in working with arrays and logical thinking when dealing with altered data structures. Solving this problem improves understanding of algorithmic complexity and optimization.
solution.js · saved

Input

[3, 4, 5, 1, 2]

Expected Output

1