Antes de aprender la búsqueda binaria, aprendamos:
¿Qué es la búsqueda?
La búsqueda es una utilidad que le permite a su usuario encontrar documentos, archivos, medios o cualquier otro tipo de datos almacenados dentro de una base de datos. La búsqueda funciona según el principio simple de hacer coincidir los criterios con los registros y mostrarlos 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 busca y obtiene 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 localice el valor requerido y se muestre 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 .
En este tutorial de algoritmos, aprenderá:
- ¿Qué es la búsqueda?
- ¿Qué es la búsqueda binaria?
- ¿Cómo funciona la búsqueda binaria?
- Ejemplo de búsqueda binaria
- ¿Por qué necesitamos la búsqueda binaria?
¿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 intermedio de la matriz ordenada de datos.
- Después de eso, el valor clave se compara con el elemento
- Si el valor de la clave es más pequeño que el elemento del medio, las búsquedas analizan los valores superiores al elemento del medio para realizar comparaciones y coincidencias.
- En caso de que el valor de la clave sea mayor que el elemento intermedio, las búsquedas analizan los valores inferiores al elemento intermedio para comparar y comparar.
Ejemplo de búsqueda binaria
Veamos el ejemplo de un diccionario. Si necesita encontrar una determinada palabra, nadie revisa 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 de 0 a 9. Ahora, se calcula la mitad de la matriz. Para hacerlo, toma los valores más a la izquierda y a la derecha del índice y los divide por 2. El resultado es 4.5, pero tomamos el valor mínimo. Por lo tanto, el medio es 4.
- El algoritmo elimina todos los elementos desde el medio (4) hasta el límite más bajo porque 59 es mayor que 24, y ahora la matriz se queda con solo 5 elementos.
- 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 medio - 1, que es igual a 6, y el valor del índice de la izquierda sigue siendo el mismo que antes, que es 5.
- En este punto, sabrá que 59 viene después de 45. Por lo tanto, el índice de la izquierda, 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 que se encuentra se convierte en el medio de la matriz.
Ejemplo 2
Veamos el siguiente ejemplo para entender el funcionamiento de la búsqueda binaria.
- Tiene una matriz de valores ordenados que van de 2 a 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 la matriz menores que el 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 buscará.
¿Por qué necesitamos la búsqueda binaria?
Las siguientes razones hacen que la búsqueda binaria sea una mejor opción para usarse como algoritmo de búsqueda:
- La búsqueda binaria funciona de manera eficiente en 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 ordenación que utilizando 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.
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 obtiene 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 en el que se encuentra el elemento requerido.
- El algoritmo binario toma la mitad de la matriz dividiendo la suma de los valores de índice de la izquierda y la derecha por 2. Ahora, el algoritmo elimina el límite inferior o superior de los elementos de la mitad de la matriz, según el 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 ordenación en lugar de utilizar comparaciones de igualdad que son lentas e inexactas.
- Una búsqueda binaria no es adecuada para datos sin clasificar.