# LeetCode 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];
};
```