Page 74 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 74
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Algoritmo 2.9. Método de búsqueda binaria
Como ejemplo se enseña este arreglo con los siguientes números:
A(n) 15 -6 0 7 9 23 54 82 101
Comparaciones 3 2 3 4 1 3 2 3 4
En el peor de los casos se requieren 4 comparaciones.
El promedio de las comparaciones es 2.77.
El óptimo es una comparación.
Si no se encuentra un elemento:
A(n) 15 -6 0 7 9 23 54 82 101
Comparaciones 3 3 3 4 4 3 3 3 4 4
El promedio es 3.4.
Este análisis trabaja para nueve elementos, pero ¿y para cualquier n? Por ejemplo, para n = 14 (figura
2.5) se tiene:
68
