Find the first and last occurrence of an element

Question:

Given an array sorted in ascending order with repeated elements and given the key. Find the first and last occurrence of that key.

Example:

array = {2, 3, 4, 4, 4, 5, 6, 7, 8};
key = 4.

Here “4” is repeated 3 times. We need to send the starting and ending occurrence of “4”

Solution:

This problem can be solved by binary search.

We need to write 2 functions, one to find the first occurrence of the number, another to find the last occurrence of the number.

So how to find the first occurrence of the number?

We can achieve this with the help of modified binary search. Here once we find any occurrence, we dont return from the function. But we modify it by saving the index in a result variable and update the end variable with mid – 1 and search the element.

We do this same for finding the last index. Here we update the start index by mid + 1 to find the last occurrence of the variable.

Solution in C++

#include <iostream>
using namespace std;

int find_first_occurrence(int arr[], int length, int key)
{
    int start = 0;
    int end = length - 1;

    int result = -1;

    while (start <= end)
    {
        int mid = (start + end)/2;

        // if key is found, ignore right part
        if (key == arr[mid])
        {
            result = mid;
            end = mid - 1;
        }

        // if key is less than the mid element, ignore right half
        else if (key < arr[mid])
            end = mid - 1;

        // if target is more than the mid element, ignore left half
        else
            start = mid + 1;
    }

    // return the first occurrence index or -1 if the element is not found
    return result;
}

int find_last_occurrence(int arr[], int length, int key)
{
    int start = 0;
    int end = length - 1;

    int result = -1;

    while (start <= end)
    {
        int mid = (start + end)/2;

        // if key is found, ignore right part
        if (key == arr[mid])
        {
            result = mid;
            start = mid + 1;
        }

        // if key is less than the mid element, ignore right half
        else if (key < arr[mid])
            end = mid - 1;

        // if target is more than the mid element, ignore left half
        else
            start = mid + 1;
    }

    // return the first occurrence index or -1 if the element is not found
    return result;
}
  

int main(void) 
{ 
    int arr[] = {1, 2, 3, 4, 4, 4, 4, 5, 6, 7 }; 
    int key = 4; 
    int size = sizeof(arr) / sizeof(arr[0]); 

    int first_occurance = find_first_occurrence(arr, size, key);

    int last_occurance = find_last_occurrence(arr, size, key);

    cout<<"The first occurrence is " <<first_occurance<<" and the last occurrence is "<<last_occurance<<endl;

    return 0; 
} 

Output:

The first occurrence is 3 and the last occurrence is 6