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.

**Problem description:**

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.

**Input:**

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.

**Output:**

You need to print the minimum value of the element.

**Examples:**

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:

answith maximum value.answith array element, update the minimum value toans.ans.Time complexityfor the brute force approach in the worst case isO(n)Space complexityfor the brute force approach in the worst case isO(1)C++ Implementation:Output:(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:

midelement, if themidelement is smaller than its left side element and right side element then will return themidelement as it is the minimum element.midelement is greater than the first element then it means element before themidelement is sorted so will search in the right side of the array.midelement.left>right.Time complexityof the above approach in the worst case isO(log(n))Space complexityof above approach in the worst case isO(1)C++ Implementation:Output: