La búsqueda binaria

La búsqueda binaria (en inglés, binary search) es la manera de encontrar un dato en una lista ordenada mirando primero el elemento del medio. Si es el buscado, se acabó. Si es mayor, el dato solo puede estar en la mitad izquierda, y si es menor, en la derecha; en cualquiera de los dos casos, media lista queda descartada con una sola comparación, y el procedimiento se repite sobre la mitad que queda. Es lo que hace cualquiera que busca una palabra en un diccionario de papel sin leerlo desde la primera página, y lo que hace el juego de adivinar un número entre uno y cien con pistas de «más alto» y «más bajo»: siete preguntas bastan siempre.

La figura de esta página hace la búsqueda paso a paso. Arriba está la lista, que puede tener quince elementos, cien, mil, un millón o mil millones. Debajo, cada fila es un paso: la franja naranja es la zona donde el número todavía puede estar, y la raya negra, el elemento del medio que se consulta. Cada fila mide la mitad que la anterior. Con mil elementos la búsqueda no pasa nunca de diez pasos; con un millón, de veinte, y con mil millones, de treinta. Buscar uno que no está cuesta lo mismo, porque la búsqueda termina cuando la franja se queda vacía, y esa es su otra virtud: dice con la misma rapidez que algo no existe y dónde habría que insertarlo para que la lista siguiera ordenada.

La cuenta que hay detrás es el logaritmo en base dos. Partir n elementos por la mitad hasta quedarse con uno exige log₂ n cortes, y como cada comparación reduce la zona a la mitad como poco, el número de pasos en el peor caso es ⌈log₂(n + 1)⌉. Es la curva que la notación O grande llama logarítmica, y su propiedad más útil se ve cambiando el tamaño en la figura: multiplicar la lista por mil añade unas diez comparaciones. Una búsqueda lineal (linear search), que mira los elementos uno por uno, necesita en promedio la mitad de la lista, y la figura dice cuántos habría mirado en cada caso. Para mil millones de elementos, la diferencia es de treinta consultas contra quinientos millones.

Tampoco se puede hacer mejor usando solo comparaciones. Cada comparación responde con una de pocas salidas, y para distinguir entre n posiciones posibles hacen falta, como mínimo, log₂ n respuestas de un bit. La búsqueda binaria alcanza ese límite, y por eso es el patrón con el que se miden las demás estructuras de búsqueda: el árbol binario de búsqueda es una búsqueda binaria guardada en forma de nodos, que funciona mientras el árbol está equilibrado, y la tabla hash consigue ir más deprisa precisamente porque no compara, sino que calcula dónde está cada cosa.

El precio está en la condición de partida. La lista tiene que estar ordenada, y ordenarla cuesta del orden de n log n operaciones, como enseñan los algoritmos de ordenación. Solo compensa si se va a buscar muchas veces, o si los datos llegan ordenados de por sí, como las fechas de un registro o las palabras de un diccionario. Además, hay que poder saltar directamente al elemento del medio, lo que es inmediato en un vector guardado en memoria contigua y en un fichero ordenado, pero imposible en una lista enlazada (linked list), que hay que recorrer desde el principio para llegar a cualquier posición.

La idea es antigua. John Mauchly la describió en 1946, en las conferencias de la Moore School de Filadelfia que fueron el primer curso sobre ordenadores electrónicos, y Donald Knuth, que reconstruyó su historia en el tercer volumen de The Art of Computer Programming en 1973, señaló lo que ocurrió después: las versiones que se publicaron durante más de una década solo funcionaban con listas de ciertas longitudes. Se quedaban en un bucle infinito cuando la zona tenía dos elementos, o se saltaban el último. Knuth atribuye a Derrick Lehmer, en 1960, la primera publicada que era correcta para cualquier tamaño, y a Hermann Bottenbruch, en 1962 y en un artículo sobre el lenguaje ALGOL 60, una variante que deja la comprobación de igualdad para el final y ahorra una comparación en cada vuelta.

Jon Bentley convirtió esa dificultad en una prueba. Contó en su columna de 1983 en Communications of the ACM que había pedido a programadores profesionales, en cursos de Bell Labs e IBM, que escribieran una búsqueda binaria con un par de horas de plazo y en el lenguaje que prefirieran, y que alrededor del noventa por ciento acabó encontrando errores en su propio programa. Los errores no estaban en la idea sino en los bordes: si la zona se cierra con alto igual al medio o con el medio menos uno, si el bucle sigue mientras bajo es menor o menor o igual que alto. Bentley usó el caso para defender que los programas se razonaran con invariantes (invariants), una afirmación que es cierta al empezar cada vuelta del bucle; aquí, que si el dato está en la lista, está entre bajo y alto.

La historia tuvo una coda veintitrés años después. En 2006, Joshua Bloch contó en el blog de investigación de Google que la búsqueda binaria que él mismo había escrito para la biblioteca estándar (standard library) de Java, y la que Bentley había demostrado correcta en su libro, fallaban con listas de más de unos mil millones de elementos. El problema estaba en una línea que parece inocente, la que calcula el medio como (bajo + alto) / 2: con enteros de 32 bits, la suma se desborda (overflows) en cuanto pasa de 2³¹ − 1, lo que puede ocurrir si la lista tiene más de 2³⁰ elementos, y el medio sale negativo. El fallo había estado nueve años en la biblioteca sin que nadie lo notara, porque en la década de 1980 una lista así era inconcebible y en la de 2000 empezaba a ser corriente. La corrección es bajo + (alto − bajo) / 2, que es la que usa la figura. La demostración de Bentley no estaba mal: suponía enteros matemáticos, y los ordenadores no los tienen.

Hoy la búsqueda binaria está en casi todas partes y casi nunca se ve. La usan las bases de datos para localizar una clave dentro de cada página de un índice, los sistemas de control de versiones (version control) como Git para encontrar el cambio que introdujo un fallo entre miles de versiones probando la del medio, y cualquier programa que calcula una raíz o un umbral acotando el intervalo donde tiene que estar la respuesta. En todos los casos funciona la misma observación de 1946: cuando las cosas están en orden, cada pregunta bien hecha vale por la mitad de todas las que quedan.