Introducción
Te has topado con un grupo de matemáticos que también son cantautores.
Han escrito una canción para cada uno de sus números favoritos y, como puedes imaginar, tienen muchísimos números favoritos (como el 0, el 73 o el 6174).
Sientes curiosidad por escuchar la canción de tu número favorito, pero con tantas canciones entre las que rebuscar, encontrar la canción adecuada podría llevarte un buen rato.
Por suerte, han organizado sus canciones en una lista de reproducción ordenada por el título, que no es más que el número sobre el que trata la canción.
Te das cuenta de que puedes usar un algoritmo de búsqueda binaria para encontrar rápidamente una canción a partir de su título.
Instrucciones
Tu tarea consiste en implementar un algoritmo de búsqueda binaria.
Un algoritmo de búsqueda binaria encuentra un elemento en un array dividiéndolo repetidamente por la mitad y conservando solo la mitad que contiene el elemento que buscamos.
Nos permite acotar rápidamente las posibles ubicaciones de nuestro elemento hasta que lo encontremos o hasta que hayamos descartado todas las posibles ubicaciones.
La búsqueda binaria solo funciona cuando un array está ordenado.
El algoritmo funciona así:
- Busca el elemento central de un array ordenado y compáralo con el elemento que buscamos.
- Si el elemento central es nuestro elemento, ¡hemos terminado!
- Si el elemento central es mayor que nuestro elemento, podemos descartar ese elemento y todos los elementos posteriores a él.
- Si el elemento central es menor que nuestro elemento, podemos descartar ese elemento y todos los elementos anteriores a él.
- Si se han descartado todos los elementos del array, el elemento no está en el array.
- En caso contrario, repite el proceso en la parte del array que no se haya descartado.
Aquí tienes un ejemplo:
Supongamos que buscamos el número 23 en el siguiente array ordenado: [4, 8, 12, 16, 23, 28, 32].
- Empezamos comparando 23 con el elemento central, 16.
- Como 23 es mayor que 16, podemos descartar la mitad izquierda del array, con lo que nos queda
[23, 28, 32].
- A continuación, comparamos 23 con el nuevo elemento central, 28.
- Como 23 es menor que 28, podemos descartar la mitad derecha del array:
[23].
- ¡Hemos encontrado nuestro elemento!
Restricciones
Rust ya incluye en su biblioteca estándar una función de búsqueda binaria. Para este ejercicio no debes usar esa función, sino otras herramientas básicas.
¿Has conseguido que los tests pasen y que el código quede limpio? Si te apetece, hay algunas cosas más que podrías probar.
- Ahora mismo, tu función find probablemente solo funcione con slices de números, pero el sistema de tipos de Rust es lo bastante flexible como para crear una función find que funcione con cualquier slice cuyos elementos se puedan ordenar.
- Además, esta función find puede funcionar no solo con slices, sino también, al mismo tiempo, con un Vec o un Array.
Para ejecutar los tests adicionales, quita la marca #[ignore] y ejecuta los tests con la funcionalidad generic, así:
$ cargo test --features generic
Después, comparte lo que piensas en un comentario del envío. ¿Ha mejorado el código con este experimento? ¿Ha empeorado? ¿Has aprendido algo con él?
