5.2 Búsqueda binaria
Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los prerrequisitos principales para la búsqueda binaria son:
La lista debe estar ordenada en un orden especifíco de acuerdo al valor de la llave.
Debe conocerse el número de registros.
Algoritmo
Se compara la llave buscada con la llave localizada al centro del arreglo.
Si la llave analizada corresponde a la buscada fin de búsqueda si no.
Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero , lo cual implica que el valor de la llave buscada no esta en la lista.
El esfuerzo máximo para este algoritmo es de log2n. El mínimo de 1 y en promedio ½ log2 n.
No comments:
Post a Comment