Para buscar un elemento dentro de un
vector (
array) hay que recorrer dicho vector, elemento a elemento, hasta encontrar el elemento en cuestión o hasta que se acabe el vector.
La
complejidad de los algoritmos se calcula teniendo en cuenta el peor caso posible. Para el caso de una búsqueda en un vector de tamaño
n, el peor caso es que el elemento no se encuentre en el vector, con lo que habría que recorrer los n elementos del vector antes de poder decir que el elemento no se encuentra en el mismo. A la complejidad de esta operación se la denomina de orden lineal (O(n)).
El algoritmo de
búsqueda binaria (o búsqueda dicotómica) es un algoritmo de búsqueda en vectores ordenados que permite disminuir la complejidad de la búsqueda en dichos vectores.
La intuición detrás de la búsqueda binaria es la misma que cuando se busca en un diccionario; cuando se va a buscar una palabra que empieza por la letra "s", nadie comienza a leerse las palabras que empiezan por la "a", luego la "b", y así en adelante. Normalmente, se abre el diccionario por la mitad y, dependiendo de si la letra inicial por la que hemos abierto es mayor o menor que la que buscamos, descartamos la mitad de las palabras de la enciclopedia y ya solo buscamos en la mitad restante.
El pseudocódigo del algoritmo de búsqueda binaria se puede encontrar, por ejemplo,
aquí. El algoritmo consiste en mantener unos índices que marcan los límites superior e inferior de la parte del vector que nos queda por analizar.
Para calcular la complejidad de este algoritmo, inicialmente en número de elementos por analizar es n. Tras la primera división, el número será como mucho n/2 (pues nos hemos quedado con la mitad de elementos); tras la segunda división, el número será como mucho n/4; y así sucesivamente. Por lo general, tras la división número i, el número de elementos por analizar será como mucho:
\[\frac{n}{2^i}\]
El peor caso se da cuando el elemento a buscar no se encuentra en el vector (es decir, cuando tras dividir los elementos por analizar nos quedemos con un número menor a 1). Por lo tanto, el número máximo de llamadas a realizar es el menor número
m tal que:
\[\frac{n}{2^m} < 1\]
Transformando esta fórmula a un
logaritmo en base 2, tenemos que:
\[n < 2^m\]
y que
\[\log n < m\]
es decir, que el número m depende, no del tamaño n del vector, sino del logaritmo de dicho n.
Es por esto que el algoritmo de búsqueda binaria tiene una complejidad de orden logarítmico (O(log n)).
Referencia:
Michael T. Goodrich y Roberto Tamassia.
Data Structures and Algorithms in Java, Fifth edition. John Wiley & Sons. 2011.
