DEV Community

Shailesh Kumar
Shailesh Kumar

Posted on

Finding Minimum in rotated sorted array

*Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.*
Example -
"""
Input: [3,4,5,1,2]
Output: 1
"""
Solution -
The naive approach is to iterate over the array and find the minimum.

return min(arr)

It takes O(n) time.
Better approach is to use binary search algo.
The intuition here is that - **
The array is rotated around a pivot. So, If we are in the left side of the the pivot, values will always be greater than the values on right side of the pivot. So, we can decide to go to the right.
Similarly, If we are on right side of the pivot, the values will be less than the left side of the pivot, also it will be less than the rightmost value.
**
If we are at the pivot then it satisfies the following condition -
arr[pivot-1] < arr[pivot] < arr[pivot + 1]
So, using above intuition we come to following solution

def findMin(self, nums: List[int]) -> int:
        arr = nums
        lo = 0
        hi = len(arr) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if lo == hi:
                return arr[lo]
            if arr[0] < arr[mid] < arr[hi]:
                return arr[0]
            if arr[mid-1] > arr[mid] and arr[mid] < arr[mid+1]:
                return arr[mid]
            else:
                if arr[mid] > arr[hi] :
                    lo = mid + 1
                else:
                    hi = mid - 1  

Top comments (0)