Algoritmos en Javascript: explicación de la búsqueda binaria

Programación

Si desea adquirir nuevas habilidades para la resolución de problemas y mejorar su conocimiento en Ciencias de la Computación, no busque más que el curso gratuito de una hora de Scrimba, The Working Developer's Guide To Algorithms. Fue diseñado para aquellos que no tienen experiencia en Ciencias de la Computación y sienten que se beneficiarían de aprender a pensar algorítmicamente.

¿Qué hace el curso?

Nuestra guía le explica cómo crear seis algoritmos de búsqueda binaria diferentes. En el estilo clásico de Scrimba, contiene un montón de desafíos en el camino, por lo que obtendrá la memoria muscular que necesita para mejorar sus habilidades como desarrollador de software y trabajar mejor con algoritmos en el futuro.

Aprenderás:

  • Búsqueda binaria
  • Notación Big O
  • Código imperativo
  • Recursividad
  • Recursión de cola
  • División de matriz
  • Vista de matriz
  • Dividir

Cada algoritmo se enseña en tres etapas:

  • Tutorial: Jonathan presenta el algoritmo de forma conceptual.
  • Implementación: Nos ensuciamos las manos creando nuestras propias versiones del algoritmo.
  • Solución: Jonathan nos muestra su implementación para comparar.

Prerrequisitos

Aprovecharás al máximo este curso si tienes un buen conocimiento de Javascript e idealmente ya estás trabajando como desarrollador o si eres un graduado de Bootcamp.

Si aún no está allí, consulte los excelentes tutoriales gratuitos de Scrimba Introducción a JavaScript e Introducción a ES6 +.

Introducción al instructor

Jonathan Lee Martin es desarrollador de software, educador web, orador y autor. Ayuda a otros desarrolladores a alcanzar sus objetivos profesionales y personales mediante la escritura, la charla, los Bootcamps inmersivos, los talleres y los tutoriales en línea.

Con clientes que incluyen empresas como NASA y HP, él es la persona ideal para llevarlo a través del viaje de aprendizaje. ¡Entonces empecemos!

Búsqueda binaria

Gráfico de búsquedas de Sweeper vs Splitter.

Haga clic en la imagen para acceder al curso.

En el primer elenco, Jonathan presenta los conceptos de notación Big-O y búsqueda binaria , el algoritmo con el que trabajaremos.

La notación Big-O es un medio para describir el peor rendimiento de un algoritmo. Una O grande de O (n) dice que si una matriz tiene una longitud de n elementos, el tiempo de ejecución será proporcional an. En otras palabras, una matriz de siete entradas tomará 7 búsquedas en el peor de los casos, así como una matriz de 7 millones de entradas tomará 7 millones de entradas en el peor de los casos. También podemos decir que el tiempo de ejecución de este algoritmo es lineal, como se ilustra en el gráfico anterior.

La búsqueda binaria es una de varias estrategias para responder a la pregunta "¿Dónde aparece este elemento en una lista?"

Al responder la pregunta, hay dos enfoques principales:

  • Barredora : Revisar cada elemento de la lista hasta encontrar el elemento correcto.
  • Splitter / Binary Search : dividir la lista por la mitad, comprobar si ha ido demasiado lejos o no lo suficiente para localizar el elemento, buscar en el lado derecho o izquierdo respectivamente y repetir hasta que se encuentre el elemento.

Podemos pensar en estos enfoques en términos de consultar una guía telefónica de papel de la vieja escuela. El enfoque de la barredora implicaría examinar todas y cada una de las entradas desde el principio hasta que se encuentre la correcta. El enfoque del divisor es el que la mayoría de la gente usaría: abrir el libro al azar y ver si necesita avanzar o retroceder hasta que se encuentre la entrada.

La búsqueda binaria es más eficiente que el enfoque de barrido, especialmente para listas más grandes. Pero solo funciona cuando la lista ya se ha ordenado.

Mientras que el enfoque de barredora tiene un tiempo de ejecución lineal (ver gráfico anterior) y Big O de O (n), el enfoque de divisor tiene un tiempo de ejecución sub-lineal y un Big O de O (log n).

Imperativo

En el primer lanzamiento de desafío, Jonathan nos anima a ensuciarnos las manos implementando la búsqueda binaria en un estilo tradicional, es decir, con una O grande de O (n), usando una cantidad fija de memoria y bucles.

Jonathan nos proporciona un conjunto de pruebas que podemos usar para asegurarnos de que nuestra solución sea exitosa y nos anima a probar el desafío nosotros mismos antes de verificar su implementación. No hay spoilers aquí, así que dirígete al elenco para probarlo tú mismo.

While this solution is short and close to the original formulation of binary search, you've probably noticed that the solution was difficult to write and not the best solution from a software craftsmanship point of view. Read on to find out ways to level up the solution...

Recursion

In this cast, we look at improving our binary search by implementing a new version with a few constraints. While our solution should still have a Big O of O(n), it should not use loops and must use recursion. All variables should be initialized with the const operator so they can't be mutated.

Jonanthan kicks us off with a skeleton version of the solution and then encourages us to try the challenge on our own:

let binarySearchWithRecursion = (array, element, compare = defaultCompare) => { return -1; }; export default binarySearchWithRecursion;

If you've completed this challenge, you've probably seen that this solution is a lot easier to read but is quite verbose. In the worst case, it can also result in infinite recursion. Continue with the course to see whether there are ways of streamlining the solution...

Tail Recursion

The challenge for the next cast is to improve our previous implementation by reducing duplication.

Jonathan warns us that the solution will look worse than the previous two solutions, however, it sets us up for some better optimizations further down the line. Head over to the course now to try the challenge for yourself and see Jonathan's solution.

Array Splitting

If you completed the previous challenge, you may have felt that we're still passing a lot of extra information into our binary search via recursion. This cast looks at a way of cleaning that up called array splitting.

We can think of array splitting in terms of our phone book example from earlier - whenever we decide that half the phone book is irrelevant, we just tear it off and throw it away. Similarly, our next solution should disregard any parts of the array which don't include our desired entry.

To help us achieve this, Jonathan starts us off with some skeleton code:

let binarySearchWithArraySplitting = ( array, element, compare = defaultCompare ) => { return -1; };

Then, as usual, he gives us free rein to try to the solution for ourselves before walking us through his own implementation.

Although this is an elegant method of binary search, because it involves making a copy of part of the array, it no longer has a Big O of O(n) and has a higher memory usage and slower run time. Continue with the course to find out whether there is a way to regain a higher performance with a similar code solution...

Array View

In this cast, we look for ways of merging the higher performance of our previous solutions with the elegance of array splitting. To do this, we create an array-like object that responds to the same methods as an array. We'll then inject this object in place of the original array.

Jonathan gets us started by initializing a function ArrayView which returns an object that expects three arguments: array, start and end. When invoked, ArrayView should return an object with four methods, length, toArray, slice and get.

export let ArrayView = ( array, start = 0, end = array.length, ) => ({ length: end - start, toArray: () => array.slice(start, end), slice: () => , get: () => , }); let binarySearchWithArrayView = (array, ...args) => binarySearchWithArraySplitting(ArrayView(array), ...args)

Our challenge is to implement the slice and get methods of ArrayView without making a copy of the original array. Click through to try it out and then view Jonathan's walkthrough.

Although this solution produces better, more readable code, it is longer than some of our previous solutions. Continue with the course to find out if we can retain the benefits of ArrayView while lifting even more of the logic out of binary search code...

Array Partition

In the final challenge cast of the course, Jonathan gives us a goal of extracting some of the cryptic bounce logic in our previous version into a data structure.

For this, we need a simple data structure which returns the middle, left or right part of an array. To start us off, Jonathan sets up a function ArrayPartition:

export let ArrayPartition = (array, pivot) => ({ left: () => array.slice(0, pivot), middle: () => array.get(pivot), right: () => array.slice(pivot + 1, array.length), });

Next, Jonathan sets up a new version of binary search called binarySearchWithPartition, which has a starting signature the same as binarySearchWithArraySplitting:

let binarySearchWithPartition = (array, element, compare = defaultCompare) => { if (array.length === 0) { return -1; } const middle = Math.floor(array.length / 2); const comparison = compare(element, array.get(middle)); if (comparison === 0) { return middle; } //bounce logic const [left, right] = comparison === -1 ? [0, middle - 1] : [middle + 1, array.length]; //end of bounce logic const subIndex = binarySearchWithArraySplitting( array.slice(left, right), element, compare ); return subIndex === -1 ? -1 : left + subIndex; }; let binarySearchWithPartitionAndView = (array, ...args) => binarySearchWithPartition(ArrayView(array), ...args);

Our challenge now is to rewrite binarySearchWithPartition with none of the bounce logic highlighted above, instead of creating an array partition and making calls to its left, middle and right methods.

Dirígete al curso ahora para probar el desafío por ti mismo. Como señala Jonathan, este desafío es complicado, por lo que está bien pasar a su solución si te quedas atascado durante demasiado tiempo, pero pruébalo primero por tu cuenta.

Envolver

Has llegado al final del curso. ¡Buen trabajo! Hemos cubierto varios enfoques de la búsqueda binaria, todos con sus propios beneficios e inconvenientes, y hemos construido una gran memoria muscular para trabajar de manera efectiva con algoritmos.

Ahora que ha visto seis enfoques diferentes para la búsqueda binaria, probablemente notará que aparecen en muchos lugares diferentes de la programación.

El curso completo de Jonathan con 10 algoritmos saldrá a fin de año, pero mientras tanto, espero que puedas poner en práctica tus nuevas habilidades de búsqueda binaria.

Feliz codificación :)