La búsqueda binaria es como buscar una palabra en un diccionario de papel: no empiezas por la A, abres por la mitad. Si la palabra que buscas va antes, te quedas con la primera mitad; si va después, con la segunda. Repites. Con mil palabras, diez aperturas. Con mil millones, treinta.
int busca(const int *v, int n, int x) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int medio = lo + (hi - lo) / 2;
if (v[medio] == x) return medio;
if (v[medio] < x) lo = medio + 1;
else hi = medio - 1;
}
return -1;
}
Fíjate en la línea del medio. Lo natural es (lo + hi) / 2, pero si lo y hi son grandes (arrays de más de mil millones de elementos con int de 32 bits), la suma se pasa del máximo y se desborda. Con enteros con signo, eso es comportamiento indefinido en C. lo + (hi - lo) / 2 nunca se sale, porque hi - lo es siempre positivo y pequeño.
Es un fallo que estuvo en bibliotecas muy usadas durante años, porque los arrays eran más pequeños de lo necesario para notarlo. Hasta que dejaron de serlo.
Dos condiciones para que funcione: el array tiene que estar ordenado, y los límites se actualizan con medio + 1 y medio - 1. Si pones lo = medio, tienes un bucle infinito esperando.