Búsqueda binaria en C++ utilizando una matriz dinámica

Introducción

La búsqueda binaria es un método de búsqueda que encuentra la posición del índice de un elemento en una matriz ordenada. En C++, podemos realizar una búsqueda binaria utilizando dos enfoques: iterativo y recursivo. En este laboratorio, realizaremos una operación de búsqueda binaria utilizando una matriz dinámica.

Crea un nuevo archivo de C++

Primero, creamos un nuevo archivo de C++ en el directorio ~/project llamado main.cpp.

touch ~/project/main.cpp

Incluye archivos de encabezado

A continuación, incluimos los archivos de encabezado necesarios: iostream, algorithm y vector.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

Crea una matriz dinámica y llénala con elementos

Creamos una matriz dinámica de enteros utilizando la clase vector y la llenamos con enteros ordenados.

vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

Implementar la función de búsqueda binaria

A continuación, implementamos la función de búsqueda binaria que busca la posición del índice de un elemento en una matriz ordenada utilizando el enfoque iterativo.

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

Llama a la función de búsqueda binaria y muestra el resultado

Finalmente, llamamos a la función de búsqueda binaria con un elemento a buscar y mostramos el resultado en la consola.

int target = 7;
int result = binarySearch(arr, target);

if (result == -1) {
    cout << "Elemento no encontrado!" << endl;
} else {
    cout << "Elemento encontrado en el índice " << result << endl;
}

Compila y ejecuta el programa

Compila y ejecuta el programa en la terminal ejecutando el siguiente comando:

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

Código final

Aquí está el código completo del archivo main.cpp:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int result = binarySearch(arr, target);

    if (result == -1) {
        cout << "Elemento no encontrado!" << endl;
    } else {
        cout << "Elemento encontrado en el índice " << result << endl;
    }

    return 0;
}

Resumen

En este laboratorio, aprendimos cómo realizar una búsqueda binaria utilizando una matriz dinámica en C++. Utilizamos el enfoque iterativo e implementamos una función de búsqueda binaria para buscar la posición del índice de un elemento en una matriz ordenada. También aprendimos cómo crear una matriz dinámica utilizando la clase vector en C++.