Listos para un #thread⚡️ para preparación de entrevistas?
Toca una herramienta que preguntan en entrevista de #algoritmos en #SiliconValley / #FAANG.
Hoy vamos a hablar de binary search (búsqueda binaria) con #Javascript!
[1/x]
Toca una herramienta que preguntan en entrevista de #algoritmos en #SiliconValley / #FAANG.
Hoy vamos a hablar de binary search (búsqueda binaria) con #Javascript!
[1/x]
Binary Search nos ayuda a encontrar elementos en una lista de una forma super optimizada.
Imaginemos que tenemos esta lista, y tenemos que encontrar el número "36"
Qué formas se te ocurren para encontrarlo?
Imaginemos que tenemos esta lista, y tenemos que encontrar el número "36"
Qué formas se te ocurren para encontrarlo?
Mmm, se me ocurre usar:
- indexOf
- filter
- includes
- incluso un for común y corriente.
El problema de todas estas soluciones, es que tienen un costo en Big O lineal. Big O(n), donde n es el tamaño de la lista.
Podemos hacerlo mucho mejor!
- indexOf
- filter
- includes
- incluso un for común y corriente.
El problema de todas estas soluciones, es que tienen un costo en Big O lineal. Big O(n), donde n es el tamaño de la lista.
Podemos hacerlo mucho mejor!
Binary Search (BS) es un algoritmo que nos ayuda a encontrar elementos descartando pedazos de la lista que no necesitamos.
Para usarlo, hay una regla importantísima: la lista tiene que estar ordenada!
Si ves una lista ordenada, es un indicador para resolver el algoritmo con BS!
Para usarlo, hay una regla importantísima: la lista tiene que estar ordenada!
Si ves una lista ordenada, es un indicador para resolver el algoritmo con BS!
Entendamos como funciona BS con un ejemplo visual.
Vamos a necesitar 3 variables.
- Un mínimo, que empezará en 0
- Un máximo, cuyo valor será el tamaño de la lista - 1
- Un pivote, que se calcula redondeando (min + max) / 2
pivote es el punto medio entre los rangos min y max!
Vamos a necesitar 3 variables.
- Un mínimo, que empezará en 0
- Un máximo, cuyo valor será el tamaño de la lista - 1
- Un pivote, que se calcula redondeando (min + max) / 2
pivote es el punto medio entre los rangos min y max!
En esta ocasión, pivote tiene un valor de 4. Este será el indice a buscar en esta ocasión.
array[4] -> 15
Estamos buscando el 36, y 15 es menor. La variable min es reemplaza por pivote + 1, y es hora de calcular pivote de nuevo!
Esto descarta la lista a la izquierda de pivote.
array[4] -> 15
Estamos buscando el 36, y 15 es menor. La variable min es reemplaza por pivote + 1, y es hora de calcular pivote de nuevo!
Esto descarta la lista a la izquierda de pivote.
Ahora pivote vale 7!
array[7] -> 54
Uhm, aún no encontramos el 36. 54 es mayor, entonces la variable max es reemplaza por pivote - 1.
Todos los números a la derecha pivote son descartados, y calculamos pivote otra vez.
Ya casi nos acercamos!
array[7] -> 54
Uhm, aún no encontramos el 36. 54 es mayor, entonces la variable max es reemplaza por pivote - 1.
Todos los números a la derecha pivote son descartados, y calculamos pivote otra vez.
Ya casi nos acercamos!
pivote ahora vale 6!
array[6] -> 36
Al fin encontramos el número! Estaba en el índice 6.
Si hubieras hecho un for, habriamos hecho 6 INTENTOS!
Con BS, solo fueron 3.
Ahora imagina este problema con un millón de números. O con un billón de datos.
Este es el poder de BS!
array[6] -> 36
Al fin encontramos el número! Estaba en el índice 6.
Si hubieras hecho un for, habriamos hecho 6 INTENTOS!
Con BS, solo fueron 3.
Ahora imagina este problema con un millón de números. O con un billón de datos.
Este es el poder de BS!
Hora de codear!
Como vimos, primero necesitamos una función binary search que va a declarar una variable min, max y pivote.
Luego nos toca hacer el ciclo para mover el pivote por la lista!
Como vimos, primero necesitamos una función binary search que va a declarar una variable min, max y pivote.
Luego nos toca hacer el ciclo para mover el pivote por la lista!
Y como vamos a movernos por la lista?
Un while nos va ayudar. Este ciclo se va a repetir una y otra vez mientras min y max no se encuentren. Si lo hacen, es porque el número a buscar no está en la lista.
Y al inicio de cada ciclo, calculamos el punto medio de min y max.
Un while nos va ayudar. Este ciclo se va a repetir una y otra vez mientras min y max no se encuentren. Si lo hacen, es porque el número a buscar no está en la lista.
Y al inicio de cada ciclo, calculamos el punto medio de min y max.
Ahora tocan las condiciones!
Recuerda: si el número que vemos en este ciclo es menor al número a buscar, reducimos max, lo que va a descartar la lista a su derecha.
Si es menor, incrementamos min y nos deshacemos de la lista a la izquierda.
Recuerda: si el número que vemos en este ciclo es menor al número a buscar, reducimos max, lo que va a descartar la lista a su derecha.
Si es menor, incrementamos min y nos deshacemos de la lista a la izquierda.
Si corremos el código, podemos ver que si encuentra el número 36!
En términos algorítmicos, que complejidad tiene binary search?
Un indexOf es Big O(n).
BS es Big O(logn)
Qué significa esto?
En términos algorítmicos, que complejidad tiene binary search?
Un indexOf es Big O(n).
BS es Big O(logn)
Qué significa esto?
Big O(n) significa que dependiendo la cantidad de elementos, es la cantidad de acciones que harás en el peor de los casos. Si tienes un millón de datos y el que buscas está al final, buscarás un millón de veces hasta encontrarlo.
Bastante lento!
Bastante lento!
Big O(logn) significa que podemos resolver un problema con solo una parte de los datos que tenemos a la mano.
Matemáticamente es algo un poco más complejo de explicar, pero quedemos con esta definición por ahora!
Matemáticamente es algo un poco más complejo de explicar, pero quedemos con esta definición por ahora!
Binary search es un algoritmo bastante común de encontrar en entrevistas. Normalmente se pregunta como un problema enfocado a esto, o como una forma para buscar una optimización al problema que estas realizando.
Conocerlo te da una ventaja para pasar la entrevista!
Conocerlo te da una ventaja para pasar la entrevista!
Y esto es todo! Nos vemos en un próximo ⚡️ thread de "como enfrentar la entrevista de algoritmos para entrar a #SiliconValley/#FAANG"!
• • •
Missing some Tweet in this thread? You can try to
force a refresh
