Page 73 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 73
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Algoritmo 2.8. Método de búsqueda secuencial recursivo
El número de comparaciones es uno de los factores más importantes para determinar la complejidad
de los métodos de búsqueda secuencial; en este se deben establecer los casos más favorables o
desfavorables que se presenten.
Al buscar un elemento en el arreglo unidimensional desordenado de N componentes, puede suceder
que ese valor no se encuentre; por lo tanto, se harán N comparaciones al recorrer el arreglo. Por otra
parte, si el elemento se encuentra en el arreglo, este puede estar en la primera posición, en la última
o en alguna intermedia. Así,
C = 1 C = (n+1)/ 2 C = n.
min med máx
El algoritmo tiene un O(n).
BúSqueda BINarIa (BINary SearcH)
El método de búsqueda binaria funciona exclusivamente con arreglos ordenados. No se puede uti-
lizar con listas simplemente ligadas ni con arreglos desordenados. Con cada iteración del método
el espacio de búsqueda se reduce a la mitad; por lo tanto, el número de comparaciones que se
deben realizar disminuye notablemente, lo cual resulta favorable cuando es más grande el tamaño
del arreglo.
La búsqueda binaria consiste en dividir el intervalo de búsqueda en dos partes, comparando el ele-
mento buscado con el que ocupa la posición central en el arreglo. Cuando estos no son iguales, se
redefinen los extremos del intervalo, tomando en cuenta si el elemento central es mayor o menor que
el buscado para disminuir el espacio de búsqueda. El proceso concluye cuando el elemento es en-
contrado o cuando el intervalo de búsqueda se anula, es vacío. El algoritmo 2.9 muestra el método
de búsqueda binaria:
67
