Enlace Patrocinado
¿Qué es la búsqueda binaria ?
Antes de seguir adelante, debe estar familiarizado con el algoritmo de búsqueda lineal.
En la búsqueda lineal , tenemos que buscar un elemento en una matriz independientemente de si está ordenado o no. La complejidad temporal de este algoritmo es O (n), donde n es el tamaño de la matriz. Pero, ¿y si tenemos una matriz ordenada? ¿Podemos mejorar la complejidad?
La respuesta es SÍ y la solución es Binary Search . Este algoritmo nos permite buscar un elemento en tiempo O (log n).
Declaración del problema : busque un elemento en una matriz ordenada de tamaño n.
Enfoque : Hay dos enfoques para resolver este problema. Una de ellas es la búsqueda lineal (que ya conoce) y la otra es la búsqueda binaria (que discutiremos a continuación).
La idea básica detrás de este algoritmo es dividir el problema en dos mitades y descartar una de ellas en cada iteración. En primer lugar, elegimos un punto de inicio y un punto final de la matriz, es decir, inicio = 0 y final = n-1. Luego encontramos su valor medio, es decir, mid = (inicio + fin) / 2. Ahora la matriz se divide en dos mitades y tenemos tres áreas para comparar. Al principio compararemos el elemento que se buscará con el elemento en el medio. Si coincide, volveremos a mediados de lo contrario, buscaremos hacia su izquierda o hacia su derecha. Ahora deberíamos tener un criterio para decidir la parte a recorrer más. Dado que es una matriz ordenada, es evidente que la parte izquierda contendrá todos los elementos más pequeños que eso y la parte derecha contendrá todos los elementos mayores que eso. Teniendo esto en cuenta, podemos movernos a la izquierda si el elemento a buscar es más pequeño que el elemento a la mitad o movernos a la derecha si el elemento a buscar es mayor que el elemento a la mitad. Este proceso continuará hasta que el punto inicial exceda el punto final.
Espero que tengas la idea básica de cómo funciona el algoritmo de búsqueda binaria. Este es un algoritmo muy importante para la programación competitiva y las entrevistas. Hay muchos problemas basados en la búsqueda binaria. Así que estad atentos para más artículos sobre búsqueda binaria.
¡Todos los mejores píos! ¡Sigue codificando! ❤