Búsqueda binaria: cuatro opciones, dieciséis bucles

Elige las cuatro opciones del código: la condición del bucle, el valor inicial de hi y las dos actualizaciones. A su lado verás cómo se ejecuta el bucle, paso a paso, sobre un vector ordenado pequeño. La comprobación lo prueba con todos los vectores hasta la longitud que indiques y con todos los valores buscados; basta un clic para cargar el primer caso que falla.

Ejemplo resuelto — Búsqueda binaria: cuatro opciones, dieciséis bucles

Casos probados	169
Punto medio calculado como lo + ((hi − lo) >> 1)	1.082.812.499

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Búsqueda binaria: cuatro opciones, dieciséis bucles

La búsqueda binaria localiza un valor x en un vector ordenado manteniendo un intervalo de índices de lo a hi que debe contener x, si está presente. En cada paso lee el elemento central, a[mid], y conserva la mitad donde puede encontrarse x. El intervalo es cerrado cuando hi representa el último índice incluido (lo <= hi, con hi empezando en n − 1), y semiabierto cuando hi representa el primer índice posterior al intervalo (lo < hi, con hi empezando en n).

Qué significa cada símbolo

lo, hi: los extremos del intervalo que queda por buscar
mid: ⌊(lo + hi)/2⌋, el índice leído en este paso
n: el número de elementos, situados en los índices de 0 a n − 1
N: la longitud del mayor vector que prueba la comprobación: todos los n de 0 a N y todos los valores buscados, (N + 1)² casos

Supone: Los valores del vector son distintos, el bucle termina en cuanto a[mid] es igual a x y, tanto en la ejecución como en la comprobación, los enteros no tienen límite superior. La tabla de desbordamiento elimina esta última suposición y calcula con 32 bits, como hace Java.
Falla cuando: Si hay valores repetidos, los dos bucles correctos siguen devolviendo un índice que contiene x, aunque no necesariamente el primero. Para hallar la primera aparición, como exige una consulta de intervalo sobre un índice ordenado, hace falta un bucle que no se detenga al encontrar una igualdad: debe ser semiabierto y aplicar hi = mid siempre que a[mid] ≥ x. Cuando termina, la respuesta es lo.

Catorce de los dieciséis bucles son incorrectos, y bastan dos elementos para demostrarlo 🖖

Cada una de las cuatro decisiones del código requiere atención, y sus dos opciones parecen razonables. La tabla situada bajo los resultados ejecuta los dieciséis bucles con todos los vectores de hasta 12 elementos y todos los valores buscados: 169 casos. Dos bucles los superan. Los demás fallan con algún vector de dos elementos como máximo; trece de los catorce lo hacen con un elemento o con el vector vacío. Limita la prueba a 1 elemento y sobreviven tres bucles; con 2 solo quedan los dos correctos. Al llegar a 256 no ha cambiado ninguno de los primeros casos fallidos. Estos casos pequeños constituyen una prueba completa, no una muestra, porque el bucle solo utiliza los valores para compararlos con x. Cualquier vector ordenado de n números distintos se comporta como 1, 3, 5… con el valor buscado en una de sus 2n + 1 posiciones posibles, ya sea sobre un elemento o en un hueco. La comprobación recorre todas esas posiciones. Jon Bentley resume la dificultad en dos fechas en Programming Pearls: «Aunque la primera búsqueda binaria se publicó en 1946, la primera que funciona correctamente para todos los valores de n no apareció hasta 1962».

Los dos bucles casi correctos fallan, como mucho, en un objetivo por vector 🖖

Pulsa Omite el último. Con lo < hi y hi = n − 1, el bucle se detiene cuando lo alcanza a hi, sin leer el elemento en el que coinciden. Todas las actualizaciones mantienen x dentro del intervalo, pero mid nunca llega a hi. Por eso solo puede quedar sin leer el elemento donde comenzó hi: encuentra todos los elementos de cualquier vector salvo el último. Pulsa Lee fuera del vector para ver el caso simétrico. Con hi = n y lo <= hi, a[n] queda dentro del intervalo, y solo un valor mayor que todos los elementos hace que lo avance hasta allí. Hasta 256 elementos, ambos bucles resuelven mal 256 y 257 de los 66.049 casos. Si se toma solo el vector de 256 elementos, fallan con el 0,19 % de los valores buscados; una prueba con cien valores aleatorios casi nunca descubriría ninguno de los dos errores. El vector vacío revela el segundo bucle en su único caso, y un vector de un elemento descubre el primero. El segundo incluso pasa inadvertido en JavaScript: a[n] es undefined, ambas comparaciones resultan falsas y el bucle asigna hi = mid − 1 antes de responder −1, correctamente. En Java, esa misma lectura lanza una excepción; en C, su comportamiento no está definido.

El bucle correcto del JDK dejó de funcionar por encima de 2³⁰ elementos 🖖

El bucle del JDK ocupa la primera fila de la tabla. Resuelve bien todos los casos que puede probar la comprobación y es el que Joshua Bloch escribió para java.util.Arrays. En Java, lo + hi es un int de 32 bits; cuando supera 2.147.483.647, desborda y se convierte en un número negativo. Un informe de error enviado a Sun el 11 de mayo de 2004 buscaba el último elemento de un vector de 1.100.000.000 bytes y obtuvo ArrayIndexOutOfBoundsException: -1064671149. La tabla de desbordamiento repite la búsqueda sin reservar memoria. En el paso 6, lo + hi vale 2.165.624.999; tras el desbordamiento y el desplazamiento, el punto medio es −1.064.671.149, la cifra del informe. En el mismo paso, lo + ((hi − lo) >> 1) da 1.082.812.499. El título del informe afirma que la búsqueda falla con vectores mayores que 1<<30, y es exacto: escribe 1.073.741.824 y el mayor valor de lo + hi será 2³¹ − 2, que cabe en el tipo. Basta un elemento más para que la búsqueda desborde en el paso 31. En su publicación de 2006 sobre el error, Bloch cuenta que permaneció oculto «unos nueve años» y señala que también aparece en la versión del propio Bentley incluida y demostrada como correcta en Programming Pearls. La frase de Bentley «asigna a m la media de l y u, redondeada hacia abajo al entero más próximo» es cierta para los enteros, pero no para los enteros de 32 bits.

Problema resuelto al detalle

Por qué solo quedan en pie dos bucles 4 pasos
Pulsa Bloqueado en lo = mid. El veredicto puede probar vectores de hasta 256 elementos, pero no más. Demuestra, para todo n, que el bucle semiabierto con lo = mid + 1 siempre termina, que el mismo bucle con lo = mid se bloquea cuando hi = lo + 1 y a[lo] < x, y qué exige ese razonamiento en el bucle cerrado.

Abre este problema en la herramienta
1. En el bucle semiabierto, el cuerpo solo se ejecuta mientras lo < hi. En tal caso, mid, redondeado hacia abajo, es mayor o igual que lo y estrictamente menor que hi.
  
  $lo < hi \Rightarrow lo \leq ⌊ \frac{lo + hi}{2} ⌋ < hi$
2. Por tanto, hi = mid reduce hi al menos en uno, y lo = mid + 1 aumenta lo al menos en uno. En ambos casos, hi − lo comienza valiendo n y disminuye al menos en uno con cada iteración. Como no puede ser negativo, el bucle termina en un máximo de n iteraciones.
  
  $hi^{'} - lo^{'} \leq (hi - lo) - 1, n \to n - 1 \to \dots \to 0$
3. Considera ahora lo = mid. Cuando hi = lo + 1, mid es ⌊(2lo + 1)/2⌋ = lo. Si a[lo] < x, la actualización no mueve lo y la siguiente iteración repite exactamente la anterior. El caso predefinido llega a ese punto con lo = 6, hi = 7, a[6] = 13 y x = 14.
  
  $hi = lo + 1 : ⌊ \frac{2 lo + 1}{2} ⌋ = lo \Rightarrow lo^{'} = lo, a [6] = 13 < 14$
4. El bucle cerrado se ejecuta mientras lo <= hi, así que admite lo = hi. Entonces mid = lo = hi: actualizar un extremo a mid no cambia nada. Las dos actualizaciones deben rebasar mid, algo seguro porque a[mid] acaba de leerse. En cambio, el intervalo semiabierto ya excluye hi. Allí, hi = mid descarta el elemento recién leído y todos los posteriores, que no pueden ser x porque a[mid] > x. Con hi = mid − 1 también se descartaría a[mid − 1], aunque podría ser x.
  
  $lo = hi \Rightarrow mid = lo = hi, [lo, hi) \to [lo, mid)$
Respuesta

Cada iteración debe acortar el intervalo, descartar únicamente índices que no puedan contener x y partir de un intervalo que abarque todo el vector. Con lo <= hi, esto exige hi = n − 1, hi = mid − 1 y lo = mid + 1; con lo < hi, exige hi = n, hi = mid y lo = mid + 1. El veredicto confirma que esos dos bucles funcionan hasta 256 elementos. El argumento vale para todo n, algo que ninguna prueba puede garantizar. En aritmética de 32 bits hace falta una premisa adicional: lo + hi debe caber en ese formato. La tercera observación muestra qué sucede cuando no se cumple.

$\leq: (n - 1, mid - 1, mid + 1) <: (n, mid, mid + 1)$

Ruta de aprendizaje

Por qué un algoritmo es correcto

Referencias (2)

The overflow in the JDK's binary search, the nine years it went unnoticed, and Bentley's proved-correct version carrying the same line; also the source of the 1946 and 1962 dates the first insight quotes from Programming Pearls: Joshua Bloch, "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken." Google Research Blog, 2 June 2006.
The bug report the page reproduces: java.util.Arrays.binarySearch on a 1,100,000,000-byte array, searching for its last element, throwing ArrayIndexOutOfBoundsException: -1064671149: OpenJDK bug JDK-5045582, "(coll) binarySearch() fails for size larger than 1<<30." Filed 11 May 2004 against Java 5.0, resolved (fixed in 6) 28 April 2006.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.

Búsqueda binaria: cuatro opciones, dieciséis bucles

Qué significa cada símbolo

Catorce de los dieciséis bucles son incorrectos, y bastan dos elementos para demostrarlo 🖖

Los dos bucles casi correctos fallan, como mucho, en un objetivo por vector 🖖

El bucle correcto del JDK dejó de funcionar por encima de 230 elementos 🖖

El bucle correcto del JDK dejó de funcionar por encima de 2³⁰ elementos 🖖