- 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.
-
Página anterior. 