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.