Instalacion y Configuración
Metodología de Programación

Implementación de la búsqueda binaria en una matriz ordenada en C++

Este ejercicio se centra en la implementación del algoritmo de búsqueda binaria, que se utiliza para encontrar eficientemente un valor objetivo dentro de un array ordenado. La búsqueda binaria funciona dividiendo repetidamente el intervalo de búsqueda por la mitad y comparando el elemento central con el objetivo. Si el objetivo coincide con el elemento central, la búsqueda se completa. Si el objetivo es menor que el elemento central, la búsqueda continúa en la mitad izquierda; de lo contrario, continúa en la mitad derecha. Este enfoque reduce significativamente la complejidad temporal a O(log n), lo que la hace mucho más rápida que la búsqueda lineal para conjuntos de datos grandes. Creará una función que recibe un array ordenado, su tamaño y el valor a buscar, y que devuelve el índice si se encuentra o -1 en caso contrario.

Grupo

Algoritmos de Búsqueda y Ordenación en C++

Ojetivo

Escriba una función llamada binarySearch que tome un array ordenado, el número de elementos y un valor objetivo a buscar. Dentro de la función, implemente el algoritmo de búsqueda binaria mediante un bucle. En la función principal, defina un array ordenado de enteros y utilice la función binarySearch para localizar un valor. Muestre el resultado imprimiendo el índice del elemento si se encuentra o un mensaje indicando que no se encontró.

Desarrolle una función que realice una búsqueda binaria en un array ordenado.

Ejemplo de Código C++

 Copiar Código C++ 
#include <iostream>   // Include the input-output stream library
using namespace std;

// Function to perform binary search on a sorted array
int binarySearch(int arr[], int size, int target) {
    int low = 0;               // Start index of the search range
    int high = size - 1;       // End index of the search range

    // Continue the loop while the range is valid
    while (low <= high) {
        int mid = low + (high - low) / 2;   // Calculate the middle index

        // If the element is found at mid
        if (arr[mid] == target) {
            return mid;       // Return the index where the target is found
        }
        // If the target is smaller, it lies in the left half
        else if (target < arr[mid]) {
            high = mid - 1;   // Adjust the end of the range
        }
        // If the target is larger, it lies in the right half
        else {
            low = mid + 1;    // Adjust the start of the range
        }
    }

    return -1;   // Return -1 if the target is not found
}

int main() {
    // Define a sorted array of integers
    int numbers[] = {3, 6, 9, 12, 15, 18, 21};
    int size = sizeof(numbers) / sizeof(numbers[0]);   // Calculate number of elements
    int target = 15;    // Value to search in the array

    // Call the binarySearch function
    int index = binarySearch(numbers, size, target);

    // Display the result
    if (index != -1) {
        cout << "Element found at index " << index << endl;
    } else {
        cout << "Element not found in the array." << endl;
    }

    return 0;   // Indicate successful program termination
}

 Salida

Element found at index 4

Comparte este ejercicio C++

Más ejercicios de programación C++Algoritmos de Búsqueda y Ordenación en C++

¡Explora el conjunto de ejercicios de programación en C++! Diseñados específicamente para principiantes, estos ejercicios te ayudarán a desarrollar una sólida comprensión de los fundamentos de C++. Desde variables y tipos de datos hasta estructuras de control y funciones simples, cada ejercicio está diseñado para desafiarte gradualmente a medida que adquieres confianza en la programación en C++.