Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element. You may assume no duplicate exists in the array.
The given problem wants you to use the concept that the array is already sorted but at some point, the array is rotated and you are required to use the concept of binary search such that instead of traversing you complete the searching operation in logarithmic time.
Note: This problem is sometimes also asked in a different way, where we have to count the number of times the sorted array is rotated either in clockwise or counterclockwise. In this question, we just need to return the index of the minimum element.
The first line of the input consists of T number of test cases, each test case consists of N size of array, and the following line consists of N number of elements.
You need to print the minimum value of the element.
Input: T=1 N=7 [4,5,6,7,0,1,2] Output: 0 0 is the minimum value in the given array. Input: T=1 N=5 [3,4,5,1,2] Output: 1 1 is the minimum value in the given array.
(a) Brute Force Approach:
In this approach, we will simply traverse from the first element of the array to the last element of the array until we get the minimum element from the array.
Following steps will be involved:
Time complexity for the brute force approach in the worst case is O(n)
Space complexity for the brute force approach in the worst case is O(1)
(b) Binary Search Approach:
In this method, we will use a binary search. If you carefully observe then we can find that the minimum element lies in the unsorted half of the array. So we need to perform binary search operation in unsorted half.
We will perform the following operation:
Time complexity of the above approach in the worst case is O(log(n))
Space complexity of above approach in the worst case is O(1)