Searching: Given an array, find the first and last position of an element in sorted array

Problem Statement:

You are given a sorted array arr[] with duplicates.

You need to find the first and last occurrence of an element ‘n’ in the given array.

Example:

Input: arr = [1, 2, 3, 4, 4, 4, 4, 4, 5, 6], n = 4
Output: 3 7

Solution 1: Brute force approach

In this approach, iterate over the array and then track the first and last occurrence of the element

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2: Binary search approach

In this approach we will find the first and last occurrence of the number using binary search separately.

Time Complexity: O(log n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
using namespace std;

int getLastIndex(vector<int> arr, int x, int n) 
{

    int low = 0;
    int high = n - 1;

    int last = -1;

    while(low <= high) 
    {

        int mid = (low + high) / 2;

        if (x == arr[mid]) 
        {
            last = mid;
            low = mid + 1;
        }

        else if (x < arr[mid])
            high = mid - 1;

        else
            low = mid + 1;
    }

    return last;
}

int getFirstIndex(vector<int> arr, int x, int n) 
{

    int low = 0;
    int high = n - 1;

    int first = -1;

    while(low <= high) 
    {

        int mid = (low + high) / 2;

        if (x == arr[mid]) 
        {
            first = mid;
            high = mid - 1;
        }

        else if (x < arr[mid])
            high = mid - 1;

        else
            low = mid + 1;
    }

    return first;
}

vector<int> solution_2 (vector<int> arr, int x, int n) 
{

    int first = getFirstIndex(arr, x, n);
    int last = getLastIndex(arr, x, n);

    vector<int> res = {first, last};

    return res;
}

vector<int> solution_1 (vector<int> arr, int x, int n) 
{

    int first = -1;
    int last = -1;

    for (int i = 0; i < n; i++) 
    {

        if (x != arr[i])
            continue;
        
        if (first == -1)
            first = i;
        
        last = i;
    }

    vector<int> res = {first, last};
    return res;
}

int main() 
{

    vector<int> arr = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6};
    int x = 4;

    int n = arr.size();

    vector<int> res = solution_1(arr, x, n);
    cout << "Solution 1 = "<< res[0] << " " << res[1]<<endl;

    res = solution_2(arr, x, n);
    cout << "Solution 2 = "<< res[0] << " " << res[1];

    return 0;
}

Output

Solution 1 = 3 7
Solution 2 = 3 7