Computacion

Análisis de la búsqueda binaria
El caso mejor se presenta cuando una coincidencia se encuentra en el punto central de la lista. En
este caso la complejidad es O(1) dado que sólo se realiza unaprueba de comparación de igualdad.
La complejidad del caso peor es O(log2 n) que se produce cuando el elemento no está en la lista o el
elemento se encuentra en la última comparación. Se puede deducirintuitivamente esta complejidad.
El caso peor se produce cuando se debe continuar la búsqueda y llegar a una sublista de longitud
de 1. Cada iteración que falla debe continuar disminuyendo lalongitud de la sublista por un
factor de 2. El tamaño de las sublistas es:
n n/2 n/4 n/8 . . . 1
La división de sublistas requiere m iteraciones, en cada iteración el tamaño de la sublista s
Se reduce ala mitad. La sucesión de tamaños de las sublistas hasta una sublista de longitud 1:
n n/2 n/2 n/23 n/24 . . . n/2m
siendo n/2m = 1.
Algoritmos de ordenación y búsqueda 193
Comparación de labúsqueda binaria y secuencial
La comparación en tiempo entre los algoritmos de búsqueda secuencial y binaria se va haciendo espectacular a medida que crece el tamaño de la lista de elementos. Tengamospresente que en el caso de la búsqueda secuencial, en el peor de los casos, coincidirá el número de elementos examinados con el número de elementos de la lista tal como representa su complejidad O(n).
Sinembargo, en el caso de la búsqueda binaria, tengamos presente, por ejemplo, que 210 = 1.024,
lo cual implica el examen de 11 posibles elementos; si se aumenta el número de elementos de una
lista a2.048 y teniendo presente que 211 = 2.048 implicará que el número máximo de elementos
examinados en la búsqueda binaria es 12. Si se sigue este planteamiento, se puede encontrar el
número m máspequeño para una lista de 1.000.000, tal que 2n ≥ 1.000.000
Es decir, 219 = 524.288, 220 = 1.048.576 y por tanto el número de elementos examinados (en el peor de los casos) es 21. La Tabla 6.2 muestra...