Page 75 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 75
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Figura 2.5. Algoritmo de búsqueda binaria con 14 elementos
Teorema. Si n está en el rango [2 , 2 ], el algoritmo de búsqueda binaria hace máximo k compara-
k-1
k
ciones, por lo que requiere máximo O (log n) para un éxito y para un fracaso (log n).
BuScaNdo el MáxIMo y MíNIMo (fINdINg tHe MaxIMuN aNd MINIMuN)
El problema es encontrar el máximo y el mínimo de un conjunto de n elementos en desorden.
El algoritmo 2.10 muestra un método directo:
Algoritmo 2.10. Método directo para el máximo y mínimo
El procedimiento requiere 2(n-1) comparaciones en el mejor, en el promedio, así como en el peor de
los casos. Puede existir una mejora al cambiar el ciclo de la siguiente forma:
69
