Question link : https://leetcode.com/problems/findminimuminrotatedsortedarray/
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 elementexample : [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 :
Top comments (1)
One good insight for similar questions: If the array is sorted, you can find a way to skip elements > using binary search.
This is similar to the question> Find peak element in a sorted array > use Binary search again to find middle element and check middle1 and middle+1 for peak invariant.