Buscar un elemento en un arreglo puede llegar muy lento, una búsqueda lineal recorre el arreglo de principio a fin hasta que encuentra el elemento. Cuando nuestro arreglo está ordenado, existe un algoritmo que nos permite encontrar el elemento muchísimo más rápido y se llama búsqueda binaria. En este artículo aprenderás a implementar la búsqueda binaria en Javascript y Python. Además, aprenderás a implementarla de forma recursiva y iterativa.

En este artículo aprenderás:

1. ¿Qué es una búsqueda binaria?
2. Comparación entre una búsqueda lineal y una binaria
3. Implementación de una búsqueda lineal
4. Implementación iterativa de una búsqueda binaria
5. Implementación recursiva de una búsqueda binaria

¿Qué es una búsqueda binaria?

La manera más fácil de entender cómo funciona una búsqueda binaria es con un ejemplo. Imagina que tienes un diccionario y estás buscando el significado de una palabra. Imagina que la palabra que buscas es 'momento'. ¿Buscarías desde la primera página de palabra en palabra hasta llegar a 'momento'? Probablemente no. Lo que harías es abrir el diccionario más o menos a la mitad y revisar en qué letra estás. Si la letra está después de la 'm' en orden alfabético te irías unas cuantas páginas hacia atrás y si la letra está antes te irías unas cuantas páginas hacia adelante. En lugar de buscar entre miles de palabras que hay en un diccionario, estaríamos buscando entre algunas páginas hasta encontrar la palabra.

En el caso de un arreglo ordenado, la búsqueda binaria funciona de la misma manera. En lugar de buscar entre todos los elementos de un arreglo, la búsqueda binaria nos permite buscar entre solamente una parte del arreglo.

El algoritmo funciona de la siguiente manera:

1. Revisamos el elemento que está exactamente a la mitad del arreglo.
2. Comparamos el elemento contra el elemento que estamos buscando.
3. Si el elemento que estamos buscando es menor que el elemento de la mitad, entonces el elemento que estamos buscando debe estar en la primera mitad del arreglo, de lo contrario debe de estar en la segunda mitad.
4. Desechamos la mitad del arreglo en la que no está el elemento que estamos buscando.
5. Repetimos el proceso con la mitad restante hasta que encontremos el elemento que estamos buscando.

Comparación entre una búsqueda lineal y una binaria

Búsqueda Lineal:

1. La búsqueda lineal es un algoritmo que recorre un arreglo de principio a fin hasta encontrar el elemento que estamos buscando. En el peor de los casos, la búsqueda lineal recorre todo el arreglo hasta encontrar el elemento que estamos buscando. En el mejor de los casos, la búsqueda lineal recorre solo la primera posición del arreglo.

2. La búsqueda lineal es un algoritmo muy sencillo de implementar pero es muy lento

3. Ejemplo: En un arrgeglo ordenado del 1 al 1,000,000 una búsqueda lineal va a hacer 500,001 comparaciones para saber si el elemento 500,001 existe.

Búsqueda Binaria:

1. La búsqueda binaria es un algoritmo que recorre un arreglo en forma de saltos en diferentes direcciones hasta encontrar el elemento que estamos buscando. En el peor de los casos, una búsqueda binaria hace 'logaritmo base 2 de n' comparaciones donde n es la longitud del arreglo ya que en cada salto el arreglo se divide a la mitad. En el mejor de los casos, una búsqueda binaria hace 1 comparación.

2. La búsqueda binaria es un algoritmo un poco más complejo de implementar pero es mucho más rápido.

3. Ejemplo: En un arreglo ordenado del 1 al 1,000,000 una búsqueda binaria va a hacer 20 comparaciones para saber si el elemento 500,001 existe.

Implementación de una búsqueda lineal

Implementación iterativa de una búsqueda binaria

Implementación recursiva de una búsqueda binaria