Introducción

Ya estamos aquí con una nueva serie de tutoriales. Esta vez el tema a tratar es la búsqueda binaria en un arreglo, tanto secuencial como recursiva o con recursión. También veremos cómo buscar sin importar si son números o cadenas.

Los enlaces a cada post están al final. Disfruta, comenta y comparte 🙂

La búsqueda binaria utiliza el método o enfoque de divide y vencerás. Debido a que el arreglo está ordenado (es un requisito) entonces podemos ir partiéndolo a la izquierda o a la derecha. Para ver si la búsqueda coincide, vemos el elemento que está a la mitad y lo comparamos.

¿Y cómo se saca la mitad del arreglo? muy fácil, sumando sus límites inferiores y superiores (es decir, la izquierda y la derecha), dividiendo entre 2 y redondeando hacia abajo.

Por poner un ejemplo, si la izquierda es 0 y la derecha es 3, entonces es:

(0 + 3) / 2 = 3 / 2 = 1.5

Luego redondeamos hacia abajo, y el índice es 1. Entonces la mitad del arreglo está en la posición 1 (recordando que los arreglos inician siempre en el índice 0)

Para obtener el elemento del medio…

Para saber cuál elemento está a la mitad sumamos los límites, los dividimos entre 2 y redondeamos hacia abajo. Por ejemplo, si nuestro arreglo es de 5 elementos: izquierda es 0, derecha es 4 (recordemos que los índices empiezan en 0), al sumarlos da 4. Los dividimos entre 2 y da 2, finalmente al redondearlo hacia abajo sigue siendo 2.

Esa es exactamente la mitad del arreglo, la posición 2. Y si el elemento que buscamos no está ahí, nos vamos a la izquierda o derecha.

El redondeo es necesario cuando tenemos un arreglo cuya longitud es par. Por ejemplo, si tenemos un arreglo de 6 entonces: izquierda es 0, derecha es 5. Al sumarlos da 5, dividimos y es 2.5 pero no existe la posición o índice 2.5; por eso es necesario redondear. Al redondear hacia abajo se convierte en 2, y si bien esa no es justamente la mitad, el algoritmo no falla, pues se irá a la izquierda o derecha de ese valor según sea el caso.

Por cierto, para redondear hacia abajo usamos las funciones que el lenguaje nos dé. La mayoría de veces es la función floor de la librería de matemáticas.

Ejemplo de búsqueda binaria

Vamos con un ejemplo simple. Tenemos el arreglo [1, 4, 5, 7, 10, 90]. Vamos a buscar el número 10.

La primera vez analizamos todo el arreglo, todavía no lo partimos. Entonces izquierda es 0, y derecha es 5. El punto medio es 2. ¿Cuál valor tenemos en la posición 2? el 5. ¿El 5 es igual a 10? No. Pero como lo que buscamos es mayor que el punto medio, inferimos que el valor que buscamos está hacia la derecha. Aquí partimos el arreglo.

Ahora ya está partido, comenzamos desde el punto medio anterior sumándole 1 hasta la derecha. Es decir, el punto medio era 2, al sumarle 1 se convierte en 3. En conclusión, la izquierda es 3 y la derecha la dejamos intacta, la cual era 5.

Entonces izquierda es 3 y derecha es 5. El punto medio es 4 (porque al redondear (3 + 5) / 2 da 4), ¿cuál valor tenemos en la posición 4? exacto, el 10. Y con eso acaba la búsqueda, pues hemos encontrado el elemento.

Búsqueda binaria en enteros

Para hacer esto es muy fácil, pues comparamos simples números con los operadores de mayor qué, menor qué y esas cosas.

Búsqueda binaria en cadenas

Esto no es tan fácil, pues algunos lenguajes de programación comparan las cadenas de distinta manera. Usaremos el mejor método en cada uno de ellos.

Algoritmo de búsqueda binaria en muchos lenguajes de programación

Se irá actualizando conforme pase el tiempo. Mientras tanto dejo estos.

1. Búsqueda binaria en arreglo de PHP usando recursividad, y también usando el ciclo While
2. JavaScript: búsqueda binaria en arreglo usando recursión y while
3. Aquí la implementación en Python
4. Con Java he hecho dos posts, uno para la búsqueda binaria en arreglos de cadenas y otro para arreglos de números
5. En Golang/Go también lo he implementado
6. Búsqueda binaria con números en C
7. Programa en C para la búsqueda binaria de cadenas.
8. Implementación en lenguaje C# c sharp
9. Más métodos vienen en camino (C# y C++)…