(a) Brute Force Approach:

The problem can be solved using the naive algorithm, we will travel from first to the last element of the array, which will take O(n) time for traversal and store the first and last occurrence of the element x.

b) Binary Search Approach:

In this approach we will use the concept of binary search, for finding the first occurrence of the element x we follow:

• If we found the element at index mid, where mid=(l+r)/2, then we will store it in some variable first, and then we will do our further search operation on the left side of the mid-point.
  i.e. r=mid-1.

For finding the last occurrence of the element x we will perform:

• If we found the element at index mid, where mid=(l+r)/2, then we will store it in some variable second, and then we will do our further search operation on the right side of the mid-point.
  i.e. l=mid+1.

Time Complexity for the above approach in the worst case is: O(logn)

Space Complexity for the above approach in the worst case is: O(1)

C++ Implementation (Brute Force Approach):

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

typedef long long ll;

void solve(ll arr[], ll n, ll x)
{
    //initialize two variable first
    //and second with -1.
    ll first = -1;
    ll last = -1;

    //alliteratively travel all elements.
    for (ll i = 0; i < n; i++) {
        //if encounter for first time.
        if (arr[i] == x and first == -1)
            first = i;
        //last occurrence.
        if (arr[i] == x and first != -1)
            last = i;
    }

    //if element is the array.
    if (first != -1)
        cout << first << " " << last << "\n";
    else
        cout << -1 << "\n";
}

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

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

        ll arr[n];

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

        //call solve function.
        solve(arr, n, x);
    }
 
    return 0;
}

Output:

Enter number of test cases: 3
Enter size of array and element x: 9 3
Enter elements: 1 2 3 3 3 3 3 3 3        
2 8
Enter size of array and element x: 5 2
Enter elements: 1 2 3 4 5
1 1
Enter size of array and element x: 3 9
Enter elements: 1 1 1
-1

C++ Implementation (Binary Search Approach):

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

typedef long long ll;

void solve(ll arr[], ll n, ll x)
{
    ll l, r;
 
    //initialize left index for
    //binary search with 0.
    l = 0;
 
    //initialize right index for
    //binary search with n-1.
    r = n - 1;
 
    //initialize first and last
    //variable with -1.
    ll first = -1;
    ll last = -1;

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

        //if array element is equal
        //to x.
        if (arr[mid] == x) {
            first = mid; //assign first index.
            r = mid - 1; //move in left range.
        }
        //if mid element is greater than
        //element x.
        if (arr[mid] > x)
            r = mid - 1;
        //if mid element is smaller than
        //element x.
        if (arr[mid] < x)
            l = mid + 1;
    }

    //again initialize left and right index.
    l = 0;
    r = n - 1;

    //perform binary search.
    while (l <= r) {
        //mid index.
        ll mid = l + (r - l) / 2;
        if (arr[mid] == x) {
            last = mid; //assign right index.
            l = mid + 1; //move in right range.
        }
        //if mid element is greater.
        if (arr[mid] > x)
            r = mid - 1;
        //if mid element is smaller.
        if (arr[mid] < x)
            l = mid + 1;
    }
    //if first is not -1.
    if (first != -1)
        cout << first << " " << last << "\n";
    else
        cout << -1 << "\n";
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;
 
    while (t--) {
        cout << "Enter size of array and element x: ";
        ll n, x;
        cin >> n >> x;
 
        ll arr[n];
 
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
 
        //call solve function.
        solve(arr, n, x);
    }
 
    return 0;
}

Output:

Enter number of test cases: 2  
Enter size of array and element x: 9 2
Enter elements: 1 2 2 2 2 2 2 2 2         
1 8
Enter size of array and element x: 5 -2
Enter elements: 1 2 3 4 5 
-1