Algorithmes en Javascript - Explication de la recherche binaire

Si vous souhaitez acquérir de nouvelles compétences en résolution de problèmes et améliorer vos connaissances en informatique, ne cherchez pas plus loin que le cours gratuit d'une heure de Scrimba, The Working Developer's Guide To Algorithms. Il a été conçu pour ceux qui n'ont pas une formation en informatique et qui estiment qu'ils gagneraient à apprendre à penser de manière algorithmique.

Que fait le cours?

Notre guide vous explique comment créer six algorithmes de recherche binaire différents. Dans le style Scrimba classique, il contient un tas de défis en cours de route, de sorte que vous gagnerez la mémoire musculaire dont vous avez besoin pour améliorer vos compétences en tant que développeur de logiciels et mieux travailler avec les algorithmes à l'avenir.

Vous apprendrez:

  • Recherche binaire
  • Notation Big O
  • Code impératif
  • Récursion
  • Récursivité de la queue
  • Division du tableau
  • Vue tableau
  • Cloison

Chaque algorithme est enseigné en trois étapes:

  • Procédure pas à pas: Jonathan présente l'algorithme de manière conceptuelle.
  • Implémentation: Nous mettons la main à la pâte en créant nos propres versions de l'algorithme.
  • Solution: Jonathan nous montre sa mise en œuvre à titre de comparaison.

Conditions préalables

Vous tirerez le meilleur parti de ce cours si vous avez une bonne compréhension de Javascript et que vous travaillez déjà idéalement en tant que développeur ou si vous êtes diplômé du Bootcamp.

Si vous n'y êtes pas encore, consultez les excellents tutoriels gratuits de Scrimba Introduction à JavaScript et Introduction à ES6 +.

Introduction à l'instructeur

Jonathan Lee Martin est un développeur de logiciels, un éducateur Web, un conférencier et un auteur. Il aide d'autres développeurs à atteindre leurs objectifs professionnels et personnels en écrivant, en parlant, en Bootcamps immersifs, en ateliers et en tutoriels en ligne.

Avec des clients, notamment des entreprises telles que la NASA et HP, il est la personne idéale pour vous accompagner tout au long du parcours d'apprentissage. Alors, commençons!

Recherche binaire

Graphique des recherches Sweeper vs Splitter.

Cliquez sur l'image pour accéder au cours.

Dans le premier casting, Jonathan présente les concepts de notation Big-O et de recherche binaire , l'algorithme avec lequel nous allons travailler.

La notation Big-O est un moyen de décrire les pires performances d'un algorithme. Un grand O de O (n) indique que si un tableau a une longueur de n éléments, le temps d'exécution sera proportionnel à n. En d'autres termes, un tableau de sept entrées prendra 7 recherches dans le pire des cas, tout comme un tableau de 7 millions d'entrées prendra 7 millions d'entrées dans le pire des cas. Nous pouvons également dire que l'exécution de cet algorithme est linéaire, comme illustré dans le graphique ci-dessus.

La recherche binaire est l'une des nombreuses stratégies permettant de répondre à la question "Où cet élément apparaît-il dans une liste?"

Pour répondre à la question, il existe deux approches principales:

  • Sweeper : vérification de chaque élément de la liste jusqu'à ce que l'élément correct soit trouvé.
  • Splitter / Recherche binaire : diviser la liste en deux, vérifier si vous êtes allé trop loin ou pas assez pour localiser l'élément, rechercher respectivement le côté droit ou gauche et répéter jusqu'à ce que l'élément soit localisé.

Nous pouvons penser à ces approches en termes de vérification d'un annuaire téléphonique à l'ancienne. L'approche de balayage impliquerait de regarder à travers chaque entrée depuis le début jusqu'à ce que la bonne soit localisée. L'approche de séparation est celle que la plupart des gens utiliseraient - ouvrir le livre au hasard et voir si vous devez avancer ou reculer jusqu'à ce que l'entrée soit localisée.

La recherche binaire est plus efficace que l'approche par balayage, en particulier pour les listes plus volumineuses. Mais cela ne fonctionne que lorsque la liste a déjà été triée.

Alors que l'approche par balayage a un temps d'exécution linéaire (voir graphique ci-dessus) et un Big O de O (n), l'approche de séparation a un temps d'exécution sous-linéaire et un Big O de O (log n).

Impératif

Dans le premier challenge cast, Jonathan nous encourage à mettre la main à la pâte en implémentant la recherche binaire dans un style traditionnel, c'est-à-dire avec un Big O de O (n), en utilisant une quantité fixe de mémoire et de boucles.

Jonathan nous fournit une suite de tests que nous pouvons utiliser pour garantir le succès de notre solution et nous encourage à relever le défi nous-mêmes avant de vérifier sa mise en œuvre. Pas de spoilers ici, alors rendez-vous au casting pour l'essayer vous-même.

Bien que cette solution soit courte et proche de la formulation originale de la recherche binaire, vous avez probablement remarqué que la solution était difficile à écrire et non la meilleure solution du point de vue de l'artisanat logiciel. Lisez la suite pour découvrir comment améliorer la solution ...

Récursion

Dans ce casting, nous cherchons à améliorer notre recherche binaire en implémentant une nouvelle version avec quelques contraintes. Alors que notre solution doit toujours avoir un Big O de O (n), elle ne doit pas utiliser de boucles et doit utiliser la récursivité. Toutes les variables doivent être initialisées avec l' constopérateur afin qu'elles ne puissent pas être mutées.

Jonanthan nous lance avec une version squelette de la solution et nous encourage ensuite à relever le défi par nous-mêmes:

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

Si vous avez réussi ce défi, vous avez probablement vu que cette solution est beaucoup plus facile à lire mais assez verbeuse. Dans le pire des cas, cela peut également entraîner une récursivité infinie. Continuez avec le cours pour voir s'il existe des moyens de rationaliser la solution ...

Récurrence de la queue

Le défi pour la prochaine distribution est d'améliorer notre implémentation précédente en réduisant la duplication.

Jonathan nous avertit que la solution sera pire que les deux solutions précédentes, mais cela nous prépare à de meilleures optimisations plus tard. Rendez-vous maintenant au cours pour essayer le défi par vous-même et voir la solution de Jonathan.

Division de la baie

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.

Rendez-vous maintenant au cours pour essayer le défi par vous-même. Comme le souligne Jonathan, ce défi est délicat, il est donc normal de passer à sa solution si vous restez bloqué trop longtemps, mais essayez d'abord par vous-même.

Emballer

Vous avez atteint la fin du cours - excellent travail! Nous avons couvert plusieurs approches de la recherche binaire, toutes avec leurs propres avantages et inconvénients, et nous avons construit une excellente mémoire musculaire pour travailler efficacement avec des algorithmes.

Maintenant que vous avez vu six approches différentes de la recherche binaire, vous remarquerez probablement qu'elle apparaît à de nombreux endroits différents de la programmation.

Le cours complet de Jonathan avec 10 algorithmes sortira à la fin de l'année, mais en attendant, j'espère que vous pourrez mettre à profit vos nouvelles compétences en recherche binaire.

Bon codage :)