Problema de la búsqueda estática Flashcards
¿Qué es el problema de la búsqueda estática y cómo se define?
El problema de la búsqueda estática consiste en encontrar la posición de un entero X en una matriz A ordenada de menor a mayor, o determinar que X no está presente en la matriz. Si X aparece más de una vez, se puede devolver cualquiera de las posiciones donde aparece. La matriz AA no se modifica durante el proceso.
¿Qué tipo de estructura debe tener el algoritmo de búsqueda binaria para funcionar correctamente?
El algoritmo de búsqueda binaria requiere que la estructura (como un arreglo o lista) esté ordenada.
¿Cuál es la técnica fundamental en la que se basa el algoritmo de búsqueda binaria?
El algoritmo de búsqueda binaria se basa en la técnica de divide y vencerás.
¿Cuáles son los pasos principales del algoritmo de búsqueda binaria?
1)Dividir la estructura en dos mitades.
2)Comparar el elemento buscado con el elemento central.
3)Descarta la mitad que no contiene el elemento buscado.
4)Repetir el proceso con la mitad restante.
¿Qué ocurre si el elemento buscado es mayor que el elemento central en la búsqueda binaria?
Si el elemento buscado es mayor que el elemento central, se descarta la primera mitad de la estructura y se ajustan las referencias para continuar la búsqueda en la mitad restante.
¿Cuál es el caso más favorable en la búsqueda binaria?
El mejor de los casos ocurre cuando el elemento buscado está en la posición central de la estructura desde el principio.
¿Qué ocurre en el peor de los casos en la búsqueda binaria?
En el peor de los casos, se realizan Log(n) iteraciones y la última iteración corresponde a un rango de un solo elemento.
¿Cómo se calcula el nuevo centro en la búsqueda binaria si el elemento buscado es menor que el elemento central?
Si el elemento buscado es menor que el elemento central, se descarta la segunda mitad y el nuevo centro se calcula con: MED = (MAX - MIN) / 2, donde MIN se ajusta a MED + 1.
¿Qué es la búsqueda por interpolación y cuándo se recomienda utilizarla?
La búsqueda por interpolación es un método que puede ofrecer un mejor tiempo de ejecución en promedio cuando los datos están ordenados uniformemente. Se recomienda cuando la distribución de los datos es bastante uniforme.
¿Cuál es la principal limitación del análisis de complejidad OO mayúscula?
El análisis OO mayúscula tiene limitaciones porque no considera constantes grandes, accesos a memoria costosos, y asume una memoria infinita, lo cual puede no ser práctico en escenarios reales.
¿Qué tipo de problemas son más adecuados para aplicar el análisis OO mayúscula?
El análisis OO mayúscula es más adecuado para entradas de grande tamaño, mientras que para entradas pequeñas, el algoritmo más simple puede ser más práctico.
