- Detalles
Antes de aprender la búsqueda 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 almacenados 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?
La búsqueda binaria es un tipo de algoritmo de búsqueda avanzada que busca y recupera datos de una lista ordenada de artículos. Su principio de funcionamiento básico es dividir los datos de la lista por la mitad hasta que se encuentre el valor requerido y se muestre al usuario en el resultado de la búsqueda. Una búsqueda binaria se denomina comúnmente búsqueda de medio intervalo o un búsqueda logarítmica.
En este tutorial de algoritmos, aprenderá:
¿Cómo funciona la búsqueda binaria?
La búsqueda binaria funciona de la siguiente manera:
- El proceso de búsqueda comienza encontrando el elemento intermedio del conjunto de datos ordenados.
- Después de eso, el valor principal se compara con el elemento
- Si el valor principal es menor que el elemento de la mediana, entonces una búsqueda analiza los valores superiores al elemento de la mediana para compararlos y hacerlos coincidir.
- Cuando el valor principal es mayor que el elemento intermedio, una búsqueda analiza los valores inferiores al elemento intermedio para realizar comparaciones y coincidencias.
Ejemplo de búsqueda binaria
Veamos un ejemplo de diccionario. Si necesita encontrar una palabra en particular, nadie revisa cada palabra de forma secuencial, sino que busca las palabras más cercanas al azar para buscar la palabra requerida.
La imagen de arriba muestra lo siguiente:
- Tiene un conjunto de 10 dígitos y necesita obtener el elemento 59.
- Todos los elementos están marcados con el índice de 0 a 9. Ahora se calcula el centro de la matriz. Para hacer eso, toma los valores izquierdo y derecho del índice y los divide por 2. El resultado es 4.5, pero tomamos el valor mínimo. Entonces 4 es el medio.
- El algoritmo elimina todos los elementos del medio (4) al límite más bajo porque 59 es mayor que 24, y ahora solo hay 5 elementos en la matriz.
- Ahora 59 es mayor que 45 y menor que 63. El medio es 7. Por lo tanto, el valor del índice de la derecha se convierte en el medio – 1, que es igual a 6, y el valor del índice de la izquierda permanece como antes, es decir, 5.
- En este punto, sabe que 59 cae después de 45. Por lo tanto, el índice de la izquierda, que es 5, también se convierte en el medio.
- Estas ediciones continúan hasta que la matriz se reduce a un elemento o el elemento encontrado está en el medio de la matriz.
Ejemplo 2
Veamos el siguiente ejemplo para comprender la búsqueda binaria de trabajo.
- Tiene un conjunto de valores ordenados entre 2 y 20 y necesita encontrar 18.
- La media de los límites inferior y superior es (l + r) / 2 = 4. El valor buscado es mayor que el medio, que es 4.
- Los valores de la matriz menores que el medio se eliminan de la búsqueda y se buscan los valores mayores que el valor promedio 4.
- Este es un proceso de uso compartido recurrente hasta que se encuentra el elemento real que se va a buscar.
¿Por qué necesitamos la búsqueda binaria?
Por las siguientes razones, es mejor utilizar la búsqueda binaria como algoritmo de búsqueda:
- La búsqueda binaria funciona de manera eficiente en datos ordenados independientemente del tamaño de los datos
- En lugar de buscar 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 compara los datos ordenados según un principio de ordenación en lugar de utilizar comparaciones de igualdad, que en su mayoría son más lentas e inexactas.
- Después de cada ciclo de búsqueda, el algoritmo divide el tamaño de la matriz en dos mitades, por lo que en la siguiente iteración solo funcionará en la otra mitad de la matriz.
Resumen
- La búsqueda es una utilidad que permite al usuario buscar documentos, archivos y otros tipos de datos. La búsqueda binaria es un tipo de algoritmo de búsqueda avanzada que busca y recupera datos de una lista ordenada de artículos.
- Las búsquedas binarias suelen ser búsquedas logarítmicas o de medio intervalo.
- Funciona dividiendo la matriz en dos mitades de cada iteración obtenida bajo el elemento requerido.
- El algoritmo binario toma la mitad de la matriz dividiendo la suma de los valores de índice a la izquierda y a la derecha por 2. Ahora, el algoritmo elimina los elementos de límite superior o inferior de los elementos de la mitad de la matriz, dependiendo de la disponibilidad elemento.
- El algoritmo accede aleatoriamente a los datos para obtener la función requerida. Esto hace que los ciclos de búsqueda sean más cortos y precisos.
- La búsqueda binaria compara los datos ordenados según un principio de ordenación en lugar de utilizar comparaciones de igualdad lentas e inexactas.
- La búsqueda binaria no es adecuada para datos no seguros.