Encontrar la primera aparición en una matriz ordenada

Introducción

En este laboratorio, aprenderemos cómo encontrar la primera aparición de un número dado en una matriz ordenada utilizando búsqueda binaria modificada en C++.

Skills Graph

El archivo de código C++

En primer lugar, creemos un archivo de código C++ llamado main.cpp en el directorio ~/project utilizando el editor de texto touch.

touch ~/project/main.cpp

Incluir los encabezados necesarios en el código

Necesitamos incluir los archivos de encabezado C++ necesarios en nuestro programa. Copia y pega el siguiente código en tu archivo main.cpp.

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

Crear una función para encontrar la primera aparición de un elemento

Crearemos una función llamada first() que toma una matriz, su índice inferior, índice superior y el elemento a buscar como entrada. La función devolverá el índice de la primera aparición del elemento. Incluye el siguiente código en el archivo main.cpp.

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

Aquí, hemos utilizado búsqueda binaria para encontrar la primera aparición del elemento. Hemos inicializado la variable res a -1 para manejar el caso en el que el elemento no está presente en la matriz. Si el elemento del medio es igual al elemento que estamos buscando, almacenamos el índice del elemento del medio en res y actualizamos el índice alto a m-1 ya que estamos buscando la primera aparición del elemento. Si el elemento del medio es mayor que el elemento que estamos buscando, actualizamos el índice alto a m-1, y si es menor que el elemento, actualizamos el índice bajo a m+1.

Implementar la función principal

En la función principal, crearemos una matriz, llamaremos a la función first creada en el Paso 3 con los argumentos adecuados y mostraremos el resultado en la consola. Copia y pega el siguiente código en la función main.

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

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

    int k = 4; //el elemento para el cual se desea encontrar el índice de la primera aparición

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

    if(f==-1)
    {
        cout << "Elemento no encontrado\n";
    }
    else
    {
        cout << "El índice de la primera aparición de " << k << " es: " << f << endl;
    }

    return 0;
}

Aquí, hemos declarado una matriz de enteros llamada a y la hemos inicializado con valores enteros ordenados. También hemos calculado el número de elementos en la matriz utilizando el operador sizeof. Luego, hemos llamado a la función first() con los argumentos adecuados y mostrado el resultado.

Compilar y ejecutar el código C++

Ahora, podemos compilar y ejecutar el código C++ utilizando los siguientes comandos.

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

Si todo sale bien, la salida será El índice de la primera aparición de 4 es: 3.

Resumen

En este laboratorio, hemos aprendido cómo encontrar la primera aparición de un número dado en una matriz ordenada utilizando búsqueda binaria modificada en C++. Hemos creado una función first() para implementar el algoritmo.