# 153. Find Minimum in Rotated Sorted Array

## The Problem

Link to original problem on Leetcode.

Suppose an array of length `n`

sorted in ascending order is **rotated** between `1`

and `n`

times. For example, the array `nums = [0,1,2,4,5,6,7] `

might become:

`[4,5,6,7,0,1,2]`

if it was rotated`4`

times.`[0,1,2,4,5,6,7]`

if it was rotated`7`

times.

Notice that **rotating** an array `[a[0], a[1], a[2], ..., a[n-1]]`

1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`

.

Given the sorted rotated array `nums`

of **unique** elements, return *the minimum element of this array*.

You must write an algorithm that runs in $O(\log n)$ time.

## Examples

Example 1:

```
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] 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.
```

Example 3:

```
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
```

## Constraints

`n == nums.length`

- 1 <=
`n`

<= 5000 - -5000 <=
`nums[i]`

<= 5000 - All the integers of nums are unique.
`nums`

is sorted and rotated between`1`

and`n`

times.

## My Solution

The naïve solution would be `return Math.min(...nums)`

. This is $O(n)$ time, because it has to check every value in the `nums`

array. We can instead use a modified binary search to get down to $O(\log n)$ time. Leetcode has a more detailed explanation with the problem on their site.

This first example uses recursion.

`const findMin = (nums) => {`

// If there's one value, return it.

// If the first value is less than the last,

// the array is sorted. Return the first value.

if (nums.length === 1 || nums[0] < nums[nums.length - 1]) {

return nums[0];

}

// Find the mid-point of the array.

const mid = Math.floor(nums.length / 2);

// If the mid-point is greater than the value to it's right,

// then that right value is the lowest. Return it.

if (nums[mid] > nums[mid + 1]) {

return nums[mid + 1];

}

// Likewise, if the mid-point is less than the value to the

// left, then the mid-point is the lowest value. Return it.

if (nums[mid - 1] > nums[mid]) {

return nums[mid];

}

// If none of the previous conditions work, we'll

// recursively call the function on a portion of the array.

// If the first value is less than the mid-point, then the

// lowest value must still be on the right-hand side.

// Call the function again with the subarray of everything

// to the right of the mid-point.

// Otherwise, it's in the left-hand side.

if (nums[0] < nums[mid]) {

return findMin(nums.slice(mid + 1));

} else {

return findMin(nums.slice(0, mid));

}

};

This problem can also be solved without recursively calling the function. Instead, we use a `while`

loop. This solution is, in my aesthetic opinion, superior to the first.

`const findMin = (nums) => {`

// Set left and right to the start and end indices of nums.

// The result will eventually be stored in the left variable.

let left = 0;

let right = nums.length - 1;

// Since an array with length 1 won't satisfy this condition,

// it skips straight to returning nums[left], which is nums[0]

while (left < right) {

const mid = Math.floor((left + right) / 2);

if (nums[mid] > nums[right]) {

// If the mid-point is greater than the value at index

// right, then we know the lowest value is on the right

// side of the array. Set the left-most index to the

// mid-point.

left = mid + 1;

} else {

// Otherise, it must be on the left side. Set the new

// right-most index to the mid-point.

right = mid;

}

}

// Eventually, nothing will remain but the lowest value

// at the left-most index.

return nums[left];

};