Algoritmo de búsqueda binaria: función, beneficios, complejidad temporal y espacial

Introducción

En cualquier sistema computacional, la búsqueda es una de las funcionalidades más críticas a desarrollar. Las técnicas de búsqueda se utilizan en la recuperación de archivos, la indexación y muchas otras aplicaciones. Hay muchas técnicas de búsqueda disponibles. Uno de los cuales es la técnica de búsqueda binaria.

Un algoritmo de búsqueda binaria funciona con la idea de ignorar la mitad de la lista en cada iteración. Sigue dividiendo la lista hasta que encuentra el valor que está buscando en una lista determinada. Un algoritmo de búsqueda binaria es una actualización rápida de un algoritmo de búsqueda lineal simple.

No se requiere experiencia en codificación. Soporte de carrera 360°. Diploma PG en Machine Learning & AI de IIIT-B y upGrad.

Funcionamiento de un algoritmo de búsqueda binaria

Lo primero que hay que tener en cuenta es que un algoritmo de búsqueda binaria siempre funciona en una lista ordenada. Por lo tanto, el primer paso lógico es ordenar la lista proporcionada. Después de ordenar, la mediana de la lista se verifica con el valor deseado.

• Si el valor deseado es igual al valor del índice central, el índice se devuelve como respuesta.

• Si el valor objetivo es inferior al índice central de la lista, se ignora el lado derecho de la lista.

• Si el valor deseado es mayor que el valor del índice central, entonces se descarta la mitad izquierda.

• Luego, el proceso se repite en listas abreviadas hasta que se encuentra el valor objetivo.

Ejemplo 1

Veamos el algoritmo con un ejemplo. Supongamos que hay una lista con los siguientes números:

1, 15, 23, 7, 6, 14, 8, 3, 27

Tomemos el valor deseado como 27. El número total de elementos en la lista es 9.

El primer paso es ordenar la lista. Después de ordenar, la lista se vería así:

1, 3, 6, 7, 8, 14, 15, 23, 27

Como el número de elementos de la lista es nueve, el índice central sería cinco. El valor en el índice cinco es 8. El valor deseado, 27, se compara con el valor 8. Primero, verifique si el valor es igual a 8 o no. En caso afirmativo, devuelva el índice y salga.

Como 27 es mayor que 8, ignoraríamos la parte izquierda y solo recorreríamos el lado derecho de la lista. La nueva lista a recorrer es:

14, 15, 23, 27

Nota: En la práctica, la lista no se trunca. Sólo se estrecha la observación. Por lo tanto, la “nueva lista” no debe confundirse con hacer una nueva lista o acortar la original. Aunque podría implementarse con una nueva lista, hay dos problemas. Primero, habrá una sobrecarga de memoria. Cada nueva lista aumentará la complejidad del espacio. Y segundo, los índices originales deben rastrearse en cada iteración.

El nuevo índice central puede tomarse como segundo o tercer elemento, según la implementación. Aquí, consideraremos el tercer elemento como central. Se compara el valor 23 con el valor 27. Como el valor es mayor que el valor central, descartaremos la mitad izquierda.

La lista a recorrer es:

27

Como la lista contiene un solo elemento, se considera que es el elemento central. Por lo tanto, comparamos el valor deseado con 27. A medida que coinciden, devolvemos el valor de índice de 27 en la lista original.

Ejemplo #2

En la misma lista, supongamos que el valor deseado es 2.

Primero, el valor central ocho se compara con 2. Como el valor deseado es más pequeño que el valor central, restringimos nuestro enfoque al lado izquierdo de la lista.

El nuevo recorrido constará de:

1, 3, 6, 7

Tomemos el elemento central como el segundo elemento. El valor deseado dos se compara con 3. Como el valor es aún más pequeño, de nuevo restringimos el enfoque al lado izquierdo de la lista.

El nuevo recorrido constará de:

1

Como la lista de desplazamiento tiene solo un elemento, el valor se compara directamente con el elemento restante. Vemos que los valores no coinciden. Por lo tanto, salimos del bucle con un mensaje de error: valor no encontrado .

Certificación avanzada de ciencia de datos, más de 250 socios de contratación, más de 300 horas de aprendizaje, 0 % de EMI

Complejidad del tiempo y el espacio

La complejidad temporal del algoritmo de búsqueda binaria es O(log n). La complejidad temporal en el mejor de los casos sería O(1) cuando el índice central coincidiría directamente con el valor deseado. El peor de los casos podría ser los valores en cualquiera de los extremos de la lista o los valores que no están en la lista.

La complejidad espacial del algoritmo de búsqueda binaria depende de la implementación del algoritmo. Hay dos formas de implementarlo:

1. método iterativo
2. método recursivo

Ambos métodos son bastante iguales, con dos diferencias en la implementación. Primero, no hay bucle en el método recursivo. En segundo lugar, en lugar de pasar los nuevos valores a la siguiente iteración del ciclo, los pasa a la siguiente recursión. En el método iterativo, las iteraciones se pueden controlar a través de las condiciones de bucle, mientras que en el método recursivo, el máximo y el mínimo se utilizan como condición límite.

En el método iterativo, la complejidad del espacio sería O(1). Mientras que en el método recursivo, la complejidad del espacio sería O(log n).

Beneficios

• Un algoritmo de búsqueda binaria es un algoritmo de búsqueda bastante simple de implementar.

• Es una mejora significativa sobre la búsqueda lineal y funciona casi igual en comparación con algunos de los algoritmos de búsqueda más difíciles de implementar.

• El algoritmo de búsqueda binaria divide la lista por la mitad en cada iteración, en lugar de peinar secuencialmente la lista. En listas grandes, este método puede ser realmente útil.

Pago: Clasificación del árbol de decisiones: todo lo que necesita saber

Conclusión

Un algoritmo de búsqueda binaria es un algoritmo ampliamente utilizado en el dominio computacional. Es un algoritmo de búsqueda amplio y preciso que puede funcionar bien en conjuntos de datos grandes y pequeños. Un algoritmo de búsqueda binaria es un algoritmo simple y confiable de implementar. Con el análisis de tiempo y espacio, los beneficios de usar esta técnica en particular son evidentes.

Si tiene curiosidad por aprender sobre ciencia de datos, consulte el Diploma PG en ciencia de datos de IIIT-B y upGrad, creado para profesionales que trabajan y ofrece más de 10 estudios de casos y proyectos, talleres prácticos, tutoría con expertos de la industria, 1- on-1 con mentores de la industria, más de 400 horas de aprendizaje y asistencia laboral con las mejores empresas.