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 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 middle-1 and middle+1 for peak invariant.