C++ Find First Occurrence of the given Number using Modified Binary Search

Hello Everyone!

In this tutorial, we will learn how to Find the First Occurrence of the given number in a Sorted Array, in the C++ programming language.

To understand the concept of Binary Search in detail, we will recommend you to visit Binary Search Algorithm, where we have explained these concepts in detail.

For better understanding, refer to the well-commented C++ code given below.

Code:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

//Program to return the first occurance of b in the vector a
int first(int a[], int l, int h, int b)
{
    int res = -1;
    while (l <= h)
    {
        int m = (l + h) / 2;

        if (a[m] == b)
        {
            res = m;
            h = m - 1;
        }
        else if (a[m] > b)
        {
            h = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }

    return res;
}

int main()
{
    cout << "\n\nWelcome to Studytonight :-)\n\n\n";
    cout << " =====  Program to find the first occurance of a given number using Modified Binary Search  ===== \n\n";

    int i, n;

    int a[] = {2, 3, 3, 4, 4, 4, 4, 4, 5};

    n = sizeof(a) / sizeof(a[0]);

    cout << "\n\nThe elements of the input sorted array are :\n\n";

    for (i = 0; i < n; i++)
    {
        cout << a[i] << "  ";
    }

    int k = 4; //the element to find the first occurance index of

    //Calling first method to return the index of the first occurance of element k
    int f = first(a, 0, n - 1, k);

    cout << "\n\nThe index of the first occurance of " << k << " is: " << f;

    cout << "\n\n\n";

    return 0;
}

Output:

We hope that this post helped you develop a better understanding of the concept of the Binary Search Algorithm and using it to find the first occurrence of the given number and its implementation in CPP. For any query, feel free to reach out to us via the comments section down below.

Keep Learning : )