(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:

• Step 1: Initialise some variable ans with maximum value.
• Step 2: Now traverse from first to the last element and compare ans with array element, update the minimum value to ans.
• Step 3: Print the ans.

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)

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        cout << "Enter elements: ";
        ll arr[n];
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        //declare temporary variable.
        ll ans = INT_MAX;
        //iterativily find minimum element.
        for (ll i = 0; i < n; i++)
            ans = min(ans, arr[i]); //assign minimum value,
        cout << ans << "\n";
    }
    
    return 0;
}

Output:

Enter number of test cases: 3
Enter size of array: 6
Enter elements: 6 5 4 1 2 3
1
Enter size of array: 5
Enter elements: 3 4 5 1 2
1
Enter size of array: 7
Enter elements: 4 5 6 7 0 1 2
0

(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:

• Step 1: First we will compare the last element with the first element of the array is already sorted then we don't need to compare further, simply return the first element.
• Step 2: If the above case fails then we need to find the mid element, if the mid element is smaller than its left side element and right side element then will return the mid element as it is the minimum element.
• Step 3: If the above case fails then we need to check in which half the minimum element lies, we will compare the first and mid element if the mid element is greater than the first element then it means element before the mid element is sorted so will search in the right side of the array.
• Step 4: if the above case fails then we will make a search in the left side of the mid element.
• Step 5: we will keep searching until left>right.

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)

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//declare solve function.
ll solve(ll arr[], ll n, ll st, ll en)
{
    //initialize left index.
    ll l = st;

    //initialize right index.
    ll r = en - 1;

    //perform binary search.
    while (l < r) {
        //find mid index.
        ll mid = l + (r - l) / 2;

        //if array is already sorted.
        if (arr[l] < arr[r])
            return arr[l];

        //if right half is unsorted
        if (arr[mid] >= arr[l])
            l = mid + 1;
        else
            r = mid;
    }
    return arr[l];
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        cout << "Enter elements: ";
        ll arr[n];
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
        cout << solve(arr, n, 0, n) << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter size of array: 6
Enter elements:4 5 6 0 1 2 
0
Enter size of array: 5
Enter elements: 3 4 5 1 2
1
Enter size of array: 7
Enter elements: 4 5 6 7 0 1 2
0