El algoritmo de búsqueda binaria

En esta lección buscarás en una lista ordenada descartando la mitad en cada paso.

Se mira el elemento central: si es el buscado, ya está; si no, se descarta la mitad que no puede contenerlo.

El código de ejemplo busca un valor y devuelve su posición, o -1 si no está.

La condición imprescindible es que la lista esté ordenada. Sobre datos desordenados el algoritmo no da error: devuelve una respuesta equivocada, que es peor. Y el bucle debe ser while (low <= high), con el igual: sin él, el caso de un solo elemento restante nunca se comprueba.

El cálculo (low + high) / 2 puede desbordar con listas enormes, y en la JVM el desbordamiento da la vuelta en silencio y produce un índice negativo. La forma segura es low + (high - low) / 2. Es el mismo fallo que estuvo veinte años en la biblioteca estándar de Java sin que nadie lo notara.

Kotlin incluye binarySearch en la biblioteca estándar, con una particularidad útil: cuando no encuentra el valor devuelve un número negativo que codifica dónde habría que insertarlo, lo que sirve para mantener una lista ordenada.