You’re given a rotated sorted array, arr, of length $n$, that is rotated clockwise between $1$ and $n$ times.

For example,

• Before rotation, arr $= [1,2,3,4,5,6,7,8]$

• After $3$ rotations, the array becomes $[6,7,8,1,2,3,4,5]$.

Mathematically, we can say that if the original array was $[a[0],a[1],a[2], ... ,a[n−1]]$, then each rotation changes the array as follows:

• First rotation: $[a[n−1],a[0],a[1],a[2],...,a[n−2]]$

• Second rotation: $[a[n−2],a[n−1],a[0],a[1],a[2],...,a[n−3]]$

• Third rotation: $[a[n−3],a[n−2],a[n−1],a[0],a[1],a[2],...,a[n−4]]$

In the example above, the minimum element is $1$ at index $3$.

For the given array, your task is to find the minimum element of this array.

Constraints:

• $n ==$ arr.length

• $1 \leq n \leq 5000$

• $-5000 \leq$ arr[i] $\leq 5000$

• All the elements of the array are distinct, that is, there are no duplicate elements.

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

A basic approach for solving this problem can be traversing the whole array and searching for the smallest element. This would require a time complexity of $O(n)$, where $n$ is the number of elements in the rotated sorted array.

Let’s see if we can do better than this.

An interesting approach to solving this problem is “modified binary search.” This approach allows us to achieve logarithmic time complexity as proposed in the “Try it yourself” section of the challenge lesson. Let’s figure out how we’ll use the modified binary search approach for this problem.

Consider the following array having the values $[1,2,3,4,5,6,−3,−2,−1,0].$