Locating First Occurrence in Sorted Array

Introduction

In this lab, we will learn how to find the first occurrence of a given number in a sorted array using modified binary search in C++.

The C++ code file

Firstly, let's create a C++ code file named main.cpp in the ~/project directory using touch text editor.

touch ~/project/main.cpp

Include necessary headers in the code

We need to include the necessary C++ header files in our program. Copy and paste the following code to your main.cpp file.

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

Create a function to find the first occurrence of an element

We will create a function called first() which takes an array, its lower index, higher index, and the element to be searched as input. The function will return the index of the first occurrence of the element. Include the following code in the main.cpp file.

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;
}

Here, we have used binary search to find the first occurrence of the element. We have initialized the res variable to -1 to handle the case when the element is not present in the array. If the middle element is equal to the element we are searching for, we store the index of the middle element in res and update the high index to m-1 as we are looking for the first occurrence of the element. If the middle element is greater than the element we are searching for, we update the high index to m-1, and if it is less than the element, we update the low index to m+1.

Implement the main function

In the main function, we will create an array, call the first function created in Step 3 with the appropriate arguments and output the result to the console. Copy and paste the below code to the main function.

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

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

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

    int f = first(a, 0, n - 1, k);

    if(f==-1)
    {
        cout << "Element not found\n";
    }
    else
    {
        cout << "The index of the first occurrence of " << k << " is: " << f << endl;
    }

    return 0;
}

Here, we have declared an array of integers named a and initialized it with sorted integer values. We have also calculated the number of elements in the array using the sizeof operator. We have then called the first() function with appropriate arguments and output the result.

Compile and run the C++ code

Now, we can compile and run the C++ code using the following commands.

g++ main.cpp -o main && ./main

If everything goes well, the output will be The index of the first occurrence of 4 is: 3.

Summary

In this lab, we have learned how to find the first occurrence of a given number in a sorted array using modified binary search in C++. We have created a first() function to implement the algorithm.