Algoritmo de búsqueda binaria con EJEMPLO

Antes de aprender a buscar binaria, aprendamos:

¿Qué es la búsqueda?

La búsqueda es una utilidad que permite al usuario encontrar documentos, archivos, medios o cualquier otro tipo de datos contenidos en una base de datos. La búsqueda funciona según el principio simple de hacer coincidir los criterios con los registros y mostrárselos al usuario. De esta forma funciona la función de búsqueda más básica.

¿Qué es la búsqueda binaria?

Una búsqueda binaria es un tipo avanzado de algoritmo de búsqueda que encuentra y recupera datos de una lista ordenada de elementos. Su principio de funcionamiento básico consiste en dividir los datos de la lista a la mitad hasta que se encuentra el valor requerido y se muestra al usuario en el resultado de la búsqueda. La búsqueda binaria se conoce comúnmente como búsqueda de medio intervalo o búsqueda logarítmica.

¿Cómo funciona la búsqueda binaria?

La búsqueda binaria funciona de la siguiente manera:

El proceso de búsqueda se inicia localizando el elemento central de la matriz de datos ordenada.
Después de eso, el valor clave se compara con el elemento.
Si el valor clave es menor que el elemento del medio, las búsquedas analizan los valores superiores hasta el elemento del medio para compararlos y compararlos.
En caso de que el valor clave sea mayor que el elemento medio, las búsquedas analizan los valores más bajos hasta el elemento medio para compararlos y compararlos.

Ejemplo de búsqueda binaria

Veamos el ejemplo de un diccionario. Si se necesita encontrar una palabra determinada, nadie recorre cada palabra de manera secuencial, sino que ubica aleatoriamente las palabras más cercanas para buscar la palabra requerida.

La imagen de arriba ilustra lo siguiente:

Tiene una matriz de 10 dígitos y es necesario encontrar el elemento 59.
Todos los elementos están marcados con el índice del 0 al 9. Ahora, se calcula la mitad de la matriz. Para hacerlo, toma los valores más izquierdo y derecho del índice y los divide por 2. El resultado es 4.5, pero tomamos el valor mínimo. Por tanto el medio es 4.
El algoritmo elimina todos los elementos desde el límite medio (4) hasta el límite inferior porque 59 es mayor que 24, y ahora la matriz queda solo con 5 elementos.
Ahora, 59 es mayor que 45 y menor que 63. El valor del medio es 7. Por lo tanto, el valor del índice derecho se convierte en el medio: 1, que es igual a 6, y el valor del índice izquierdo sigue siendo el mismo que antes, que es 5.
En este punto, sabes que 59 viene después de 45. Por lo tanto, el índice izquierdo, que es 5, también se convierte en medio.
Estas iteraciones continúan hasta que la matriz se reduce a un solo elemento, o el elemento a encontrar se convierte en el centro de la matriz.

Ejemplo

Veamos el siguiente ejemplo para entender el funcionamiento de la búsqueda binaria.

Tiene una serie de valores ordenados que van del 2 al 20 y necesita ubicar 18.
El promedio de los límites inferior y superior es (l + r) / 2 = 4. El valor que se busca es mayor que el medio que es 4.
Los valores de matriz menores que el valor medio se eliminan de la búsqueda y se buscan los valores mayores que el valor medio 4.
Este es un proceso de división recurrente hasta que se encuentra el elemento real que se va a buscar.

¿Por qué necesitamos la búsqueda binaria?

Las siguientes razones hacen que la búsqueda binaria sea una mejor opción para utilizar como algoritmo de búsqueda:

La búsqueda binaria funciona de manera eficiente con datos ordenados sin importar el tamaño de los datos.
En lugar de realizar la búsqueda revisando los datos en una secuencia, el algoritmo binario accede aleatoriamente a los datos para encontrar el elemento requerido. Esto hace que los ciclos de búsqueda sean más cortos y precisos.
La búsqueda binaria realiza comparaciones de los datos ordenados basándose en un principio de ordenamiento en lugar de utilizar comparaciones de igualdad, que son más lentas y en su mayoría inexactas.
Después de cada ciclo de búsqueda, el algoritmo divide el tamaño de la matriz a la mitad, por lo que en la siguiente iteración funcionará solo en la mitad restante de la matriz.

Conoce nuestro próximo tutorial de Búsqueda lineal: Python, C++ Ejemplo

Resumen

La búsqueda es una utilidad que permite al usuario buscar documentos, archivos y otros tipos de datos. Una búsqueda binaria es un tipo avanzado de algoritmo de búsqueda que busca y recupera datos de una lista ordenada de elementos.
La búsqueda binaria se conoce comúnmente como búsqueda de medio intervalo o búsqueda logarítmica.
Funciona dividiendo la matriz por la mitad en cada iteración bajo la cual se encuentra el elemento requerido.
Un espacio para hacer una pausa, reflexionar y reconectarse en privado. algoritmo binario toma la mitad de la matriz dividiendo la suma de los valores de índice izquierdo y derecho por 2. Ahora, el algoritmo elimina el límite inferior o superior de elementos de la mitad de la matriz, dependiendo del elemento que se encuentre.
El algoritmo accede aleatoriamente a los datos para encontrar el elemento requerido. Esto hace que los ciclos de búsqueda sean más cortos y precisos.
La búsqueda binaria realiza comparaciones de los datos ordenados basándose en un principio de ordenamiento en lugar de utilizar comparaciones de igualdad que son lentas e inexactas.
Una búsqueda binaria no es adecuada para datos no ordenados.

Te podría gustar: