Trampas de la búsqueda binaria: desbordamiento del punto medio y límites con error de uno

Qué es

La búsqueda binaria encuentra una posición en datos ordenados dividiendo repetidamente a la mitad el rango de candidatos. Se repiten tres errores. Primero, el desbordamiento del punto medio: la entrada citada del blog de Google Research describe cómo (low + high) / 2 falla en el binarySearch del JDK en cuanto la suma supera el máximo int, y ofrece low + ((high - low) / 2) o (low + high) >>> 1 como soluciones. Segundo, la convención de límites: que high sea inclusivo o exclusivo determina la condición del bucle y las actualizaciones; mezclar convenciones produce bucles infinitos o salta un elemento. Tercero, los duplicados: el bisect de Python documenta bisect_left (punto de inserción antes de las entradas iguales) y bisect_right (después), que es la diferencia entre «primera coincidencia» y «posición tras la última coincidencia». El sort.Search de Go evita la mayor parte de esto pidiendo el índice más pequeño en [0, n) en el que un predicado monótono se vuelve verdadero.

Por qué importa

Esta rutina aparece en los cursores de paginación, las búsquedas en series temporales, las comprobaciones de rango de versión, las búsquedas al estilo git bisect sobre compilaciones, y muchas tareas de «encontrar el primero que falla». Un límite equivocado actúa en silencio: los resultados se desvían en uno solo para algunas entradas, típicamente el primer o el último elemento.

Cómo aplicarlo

• Preferir la función de biblioteca (bisect, sort.Search, Arrays.binarySearch); escribir una propia solo cuando el predicado no es una búsqueda en un arreglo.
• Usar la forma con predicado: encontrar el primer índice en el que pred(i) es verdadero, exigiendo que pred sea falso y después verdadero a lo largo del rango. El límite inferior, el límite superior y la «primera versión que falla» son casos particulares.
• Usar un intervalo semiabierto: lo, hi = 0, n; mientras lo < hi: mid = lo + (hi - lo) // 2; si pred(mid): hi = mid, si no lo = mid + 1; devolver lo. El + 1 en la rama else garantiza el avance.
• Probar los casos límite: entrada vacía, un elemento, objetivo por debajo del primero y por encima del último, todos los elementos iguales, objetivo en el índice 0 y en n-1.
• Verificar que los datos están ordenados bajo la misma comparación que se usa para buscar (el key= de bisect debe coincidir con la clave de ordenación).

Trampas

Los enteros de Python no desbordan, pero los errores de límites siguen presentes. Una búsqueda sobre floats se rompe en presencia de NaN, porque las comparaciones dejan de ser un orden. Unos datos ordenados con colación de configuración regional y buscados byte a byte no están ordenados para esa búsqueda. bisect_left devuelve un punto de inserción para valores ausentes, no -1: hay que comprobar i < len(a) and a[i] == x. La búsqueda binaria sobre una lista enlazada es lineal, porque indexar en ella también lo es.