Introducción
Te topaste con un grupo de matemáticos que también son cantautores.
Escribieron 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).
Tienes curiosidad por escuchar la canción de tu número favorito, pero con tantas canciones entre las que buscar, encontrar la correcta podría tardar un rato.
Por suerte, organizaron sus canciones en una lista de reproducción ordenada por el título, que es simplemente 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 del título.
Instrucciones
Tu tarea es 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 reducir rápidamente las posibles ubicaciones de nuestro elemento hasta que lo encontramos, o hasta que hayamos descartado todas las ubicaciones posibles.
La búsqueda binaria solo funciona cuando el array está ordenado.
El algoritmo funciona así:
- Encuentra el elemento del medio de un array ordenado y compáralo con el elemento que buscamos.
- Si el elemento del medio es el que buscamos, ¡ya terminamos!
- Si el elemento del medio es mayor que el que buscamos, podemos descartar ese elemento y todos los elementos posteriores a él.
- Si el elemento del medio es menor que el que buscamos, podemos descartar ese elemento y todos los elementos anteriores a él.
- Si ya descartamos todos los elementos del array, entonces el elemento no está en el array.
- De lo contrario, repite el proceso en la parte del array que no hayas 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 del medio, 16.
- Como 23 es mayor que 16, podemos descartar la mitad izquierda del array, y nos queda
[23, 28, 32].
- Después comparamos 23 con el nuevo elemento del medio, 28.
- Como 23 es menor que 28, podemos descartar la mitad derecha del array:
[23].
- Encontramos el elemento que buscábamos.
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 solo otras herramientas básicas.
¿Lograste que pasaran los tests y que el código quedara limpio? Si quieres, hay
algunas cosas adicionales que podrías probar.
- Por ahora, tu función find seguramente 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
con un Vec o un Array.
Para ejecutar los tests adicionales, quita el flag #[ignore] y ejecuta los tests con
la feature generic, así:
$ cargo test --features generic
Luego comparte lo que piensas en un comentario sobre tu envío. ¿Este experimento
mejoró el código? ¿Lo empeoró? ¿Aprendiste algo con él?
