Búsqueda lineal vs. binaria
Búsqueda lineal vs. binaria es un experimento interactivo de Algoritmos en acción, una simulación gratuita de StudyFi Lab que funciona directamente en el navegador.
La búsqueda lineal revisa los elementos uno a uno, así que en el peor caso necesita n pasos: O(n). La búsqueda binaria solo funciona en un arreglo ordenado: mira el centro y, según el resultado, descarta una mitad entera. Tras cada paso queda como mucho la mitad, por eso bastan como máximo ⌈log₂(n+1)⌉ pasos: O(log n). Con 40 elementos son 6 pasos en vez de 40.
Prueba esto: Pon 40 elementos y busca el último valor. Luego elige un número que no esté en el arreglo: ¿cuántos pasos necesita cada búsqueda para saberlo?
Preguntas frecuentes
¿Qué muestra el experimento «Búsqueda lineal vs. binaria»?
La búsqueda lineal revisa los elementos uno a uno, así que en el peor caso necesita n pasos: O(n). La búsqueda binaria solo funciona en un arreglo ordenado: mira el centro y, según el resultado, descarta una mitad entera. Tras cada paso queda como mucho la mitad, por eso bastan como máximo ⌈log₂(n+1)⌉ pasos: O(log n). Con 40 elementos son 6 pasos en vez de 40.
¿Cómo pruebo «Búsqueda lineal vs. binaria»?
Pon 40 elementos y busca el último valor. Luego elige un número que no esté en el arreglo: ¿cuántos pasos necesita cada búsqueda para saberlo?
¿Estudias para un examen?
Sube tus apuntes y StudyFi los convierte en tarjetas, tests y pódcasts.