## DEV Community

Vishva Thejeshwar

Posted on

# Find the smallest number in a rotated sorted array

Rotated sorted array : a sorted array which is rotated ( ¯\_(ツ)_/¯ ).

Leet code has a better definition : an array sorted in ascending order is rotated at some pivot

Sorted array : [1,2,3,4,5,6,7]
Rotated sorted array :
1 rotation : [7,1,2,3,4,5,6]
2 rotations : [6,7,1,2,3,4,5]
3 rotations : [5,6,7,1,2,3,4]
7 rotations : [1,2,3,4,5,6,7] - the same sorted array

To find the smallest element in the given array :

Approach 1 : Brute force - Go through the array once and find the minimum element - O(n)

Approach 2 : Binary Search O(log n)

1. If the number of elements is 1 , return the element

2. Choose a element at a mid point

3. If the first element of the array is greater than mid element, then the minimum element should be in between the first element and mid element

``````example : [6,7,0,1,2,3,4]
mid element is 1
first element is 6
smallest element 0 is between first element and mid element [7,0,1]
The first element can be excluded because we already know that mid element is smaller than the first and we only need smallest element
``````
4. If the first element is smaller than the n, then two possibilities arise:
4.1 The array may already be sorted : Check if the last element is greater than the element at mid, if yes return the first element

``````example : [1,2,3,4,5,6,7]
mid element is 4
first element is 1
last element is 7
last element is greater than the mid, so return the first element i.e.1
``````

4.2 The minimum element is present between the mid element and the end of the array

``````example : [2,4,5,6,7,0,1]
mid element is 6
first element is 2
last element is 1
last element is lesser than the mid, so smallest element is between mid and the end [7,0,1]
the mid element can be excluded because we already know the last element is lesser than the mid
``````

Final code :