Find the smallest number in a rotated sorted array

Vishva Thejeshwar — Wed, 01 May 2019 06:08:23 +0000

Question link : https://leetcode.com/problems/find-minimum-in-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)

If the number of elements is 1 , return the element
Choose a element at a mid point

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

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 :

DEV Community: Vishva Thejeshwar

Find the smallest number in a rotated sorted array