Búsqueda secuencial frente a búsqueda binaria – contar comparaciones
InformáticaAlgoritmos y resolución de problemasEdades 12–13
Úsala con tu clase: tus estudiantes la abren con un enlace o un código QR, sin crear una cuenta.
Sigue con Algoritmos y resolución de problemas
El mismo arreglo y el mismo valor buscado se procesan a la vez con búsqueda secuencial (recorriendo desde el principio) y con búsqueda binaria (dividiendo el intervalo a la mitad en un arreglo ordenado). Los estudiantes pulsan Paso o Reproducir para ver la celda que se compara, el intervalo que se descarta y el número de comparaciones de cada algoritmo; al hacer clic en una celda cambia el valor buscado, y al desactivar el orden se ve por qué la búsqueda binaria deja de funcionar.
Lección: Algoritmo de búsqueda secuencial; algoritmo de búsqueda binaria
Qué muestra
La búsqueda secuencial revisa los elementos uno a uno desde el principio, así que en el peor caso necesita tantas comparaciones como elementos haya. La búsqueda binaria compara el valor buscado con el elemento central de un arreglo ordenado y descarta la mitad que no puede contenerlo, por lo que necesita como mucho unas log₂n + 1 comparaciones: solo cinco para dieciséis elementos. Contar las comparaciones de ambos algoritmos sobre el mismo arreglo muestra por qué la binaria gana en listas largas y por qué depende por completo de que los datos estén ordenados.
Cómo usarla
Pon Algoritmo en Ambos (comparar), elige el Número de elementos y pulsa Paso para seguir cada comparación: la celda resaltada, los marcadores low, mid y high y la parte del arreglo descartada. Haz clic en una celda para cambiar el valor buscado, o usa Reproducir para una ejecución completa. Prueba un valor cerca del principio del arreglo y luego desactiva Arreglo ordenado de forma ascendente para ver por qué la búsqueda binaria deja de servir.
Parámetros que puedes cambiar
- Número de elementos 5–20
- Valor buscado (0 = elegir al azar del arreglo) 0–99
- Algoritmo Ambos (comparar), Búsqueda secuencial, Búsqueda binaria
- Arreglo ordenado de forma ascendente
- Velocidad 1–5 pasos/s
Preguntas para explorar
- ¿Cuántas comparaciones necesita como máximo la búsqueda binaria para encontrar un valor en un arreglo de 16 elementos?
- ¿Para qué valores buscados necesita la búsqueda secuencial menos comparaciones que la binaria?
- ¿Por qué no se puede usar la búsqueda binaria cuando el arreglo no está ordenado?
