Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C

Búsqueda binaria y lower bound en C

La búsqueda binaria reduce repetidamente a la mitad un intervalo de búsqueda ordenado. El ejemplo implementa lower bound: el índice del primer elemento que no es menor que la clave, o n si no existe. Trata los duplicados, la entrada vacía y el cálculo seguro del punto medio.

Versión: C23; repository compiler flag, production runtime not attested

Sintaxis

size_t lower_bound_int(const int *a, size_t n, int key);

La búsqueda binaria elige el punto medio de un intervalo y descarta la mitad que no puede contener el resultado buscado. La precondición de entrada ordenada significa aquí que a[0..n) está ordenado de forma no decreciente según la misma comparación que usa la búsqueda. La función no comprueba esta condición; una entrada desordenada puede producir un resultado incorrecto.

La función de ejemplo lower_bound_int implementa lower bound: devuelve el primer índice pos para el que a[pos] >= key, o n si no existe ninguno. Si hay duplicados, señala la primera aparición. El índice por sí solo no confirma que la clave esté presente: use la comprobación pos < n && a[pos] == key. La evaluación de cortocircuito evita que esta comprobación lea a[n].

El bucle mantiene el intervalo semiabierto [lo, hi): los elementos anteriores a lo son menores que key, y los elementos desde hi hasta n no son menores que key. La instrucción hi = mid conserva un posible primer resultado, mientras que lo = mid + 1 omite un elemento demasiado pequeño. La expresión lo + (hi - lo) / 2 evita el desbordamiento al sumar los extremos. Cuando lo == hi, ambos límites determinan el resultado.

Para n > 0, a debe proporcionar al menos n elementos válidos, que no deben cambiar durante la búsqueda. Para n == 0, esta implementación acepta NULL y devuelve 0 sin leer memoria. En un array, el tiempo es O(log n) para n >= 2 y el espacio auxiliar es O(1); no se incluye la ordenación previa. C23 es el objetivo de las opciones del compilador del repositorio, no una certificación del entorno de ejecución en producción.

Ejemplos

#include <stddef.h>
#include <stdio.h>

static size_t lower_bound_int(const int *a, size_t n, int key)
{
    size_t lo = 0;
    size_t hi = n;

    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int main(void)
{
    const int a[] = {1, 3, 3, 7};
    const size_t n = sizeof a / sizeof a[0];
    const int keys[] = {3, 4, 9};

    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i) {
        size_t pos = lower_bound_int(a, n, keys[i]);
        int found = pos < n && a[pos] == keys[i];
        printf("key=%d pos=%zu found=%d\n", keys[i], pos, found);
    }
    printf("empty pos=%zu\n", lower_bound_int(NULL, 0, 3));
    return 0;
}

Resultado

key=3 pos=1 found=1
key=4 pos=3 found=0
key=9 pos=4 found=0
empty pos=0

El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.

Fuentes