CodeUtility
Haz que programar sea más fácil.
Algoritmos en C/C++

La búsqueda binaria en C y C++

En esta lección vas a buscar en un arreglo ordenado en O(log n), con un bucle escrito a mano en C y con std::lower_bound en C++.

Introducción

La búsqueda binaria compara el valor buscado con el elemento que está en el medio de la zona de búsqueda y descarta la mitad que no puede contenerlo. Al repetir la operación, la zona se reduce muy rápido, pero los datos de entrada tienen que estar ordenados.

Puntos importantes

  • Prueba con una entrada vacía, un solo elemento, valores repetidos y datos ya ordenados.
  • Primero haz que el código sea correcto y después optimízalo.
  • En código real, usa preferentemente las funciones ya hechas de la biblioteca estándar.

Visualizador de La búsqueda binaria en C y C++

O(log n)

Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.

Ejemplos de código C y C++

C
Ejecutar →
main.c
#include <stdio.h>

int search(const int *values, int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}

int main(void) {
    int values[] = {3, 7, 11, 16, 23, 28};
    printf("index=%d\n", search(values, 6, 23));
}
Resultado de la ejecución
index=4
C++
Ejecutar →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{3, 7, 11, 16, 23, 28};
    auto match = std::lower_bound(values.begin(), values.end(), 23);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}
Resultado de la ejecución
index=4

Comparación entre C y C++

En la versión de C, la posición del medio se calcula con low + (high - low) / 2 en lugar de (low + high) / 2, para evitar un desbordamiento cuando los índices son muy grandes. En cada comparación, low o high se mueve hacia la mitad que queda. La versión de C++ usa std::lower_bound para encontrar la primera posición que no es menor que el valor buscado. Las dos tienen una complejidad de O(log n).

C

Los bucles, los punteros, las longitudes y los búferes temporales se escriben de forma explícita.

C++

Los iteradores y los algoritmos estándar separan el procesamiento de la forma en que se guardan los datos.

Ejercicios de práctica

Ejecuta las dos versiones y después modifica el código para ver la diferencia de seguridad que aporta cada lenguaje.

  • Sigue cada comparación en papel.
  • Prueba con valores repetidos y con valores muy grandes y muy pequeños.
  • Mide el tiempo de ejecución de tu código y compáralo con la biblioteca estándar.

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos