Find Minimum in Rotated Sorted Array

Try to solve the Find Minimum in Rotated Sorted Array problem.

Statement

You’re given a rotated sorted array, arr, of length nn, that is rotated clockwise between 11 and nn times.

For example,

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

  • After 33 rotations, the array becomes [6,7,8,1,2,3,4,5][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[n1]][a[0],a[1],a[2], ... ,a[n−1]], then each rotation changes the array as follows:

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

  • Second rotation: [a[n2],a[n1],a[0],a[1],a[2],...,a[n3]][a[n−2],a[n−1],a[0],a[1],a[2],...,a[n−3]]

  • Third rotation: [a[n3],a[n2],a[n1],a[0],a[1],a[2],...,a[n4]][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 11 at index 33.

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

Constraints:

  • n==n == arr.length

  • 1n10001 \leq n \leq 1000

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

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

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.