C++ Encuentra la primera ocurrencia del número dado usando la búsqueda binaria modificada

C++ Encuentra la primera ocurrencia del número dado usando la búsqueda binaria modificada

¡Hola a todos!

En este tutorial, aprenderemos a encontrar la primera ocurrencia del número dado en una matriz ordenada , en el lenguaje de programación C++.

Para entender el concepto de Búsqueda Binaria en detalle, le recomendamos visitar Algoritmo de Búsqueda Binaria, donde hemos explicado estos conceptos en detalle.

Para una mejor comprensión, consulte el código C++ bien comentado que se proporciona a continuación.

Código:

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

Salida:

Esperamos que esta publicación lo haya ayudado a desarrollar una mejor comprensión del concepto del algoritmo de búsqueda binaria y usarlo para encontrar la primera aparición del número dado y su implementación en CPP. Para cualquier consulta, no dude en comunicarse con nosotros a través de la sección de comentarios a continuación.

Sigue aprendiendo:)