Algorithmen in Javascript - Binäre Suche erklärt

Wenn Sie neue Fähigkeiten zur Problemlösung erwerben und Ihre Informatikkenntnisse verbessern möchten, ist der kostenlose einstündige Kurs von Scrimba, The Working Developer's Guide To Algorithms, genau das Richtige für Sie. Es wurde für diejenigen entwickelt, die keinen Hintergrund in Informatik haben und das Gefühl haben, vom Lernen des algorithmischen Denkens zu profitieren.

Was macht der Kurs?

Unser Leitfaden führt Sie durch die Erstellung von sechs verschiedenen binären Suchalgorithmen. Im klassischen Scrimba-Stil enthält es eine Reihe von Herausforderungen, sodass Sie das Muskelgedächtnis gewinnen, das Sie benötigen, um Ihre Fähigkeiten als Softwareentwickler zu verbessern und künftig besser mit Algorithmen zu arbeiten.

Du wirst lernen:

  • Binäre Suche
  • Big O-Notation
  • Imperativer Code
  • Rekursion
  • Schwanzrekursion
  • Array-Aufteilung
  • Array-Ansicht
  • Partition

Jeder Algorithmus wird in drei Stufen unterrichtet:

  • Exemplarische Vorgehensweise: Jonathan führt den Algorithmus konzeptionell ein.
  • Implementierung: Wir machen uns die Hände schmutzig, indem wir unsere eigenen Versionen des Algorithmus erstellen.
  • Lösung: Jonathan zeigt uns seine Implementierung zum Vergleich.

Voraussetzungen

Sie werden das Beste aus diesem Kurs herausholen, wenn Sie ein gutes Verständnis von Javascript haben und idealerweise bereits als Entwickler arbeiten oder ein Bootcamp-Absolvent sind.

Wenn Sie noch nicht dort sind, lesen Sie die großartigen kostenlosen Tutorials von Scrimba, Einführung in JavaScript und Einführung in ES6 +.

Einführung in den Ausbilder

Jonathan Lee Martin ist Softwareentwickler, Web-Pädagoge, Redner und Autor. Er hilft anderen Entwicklern, ihre beruflichen und persönlichen Ziele zu erreichen, indem er schreibt, spricht, immersive Bootcamps, Workshops und Online-Tutorials durchführt.

Mit Kunden wie Unternehmen wie der NASA und HP ist er genau die richtige Person, um Sie durch die Lernreise zu führen. Also lasst uns anfangen!

Binäre Suche

Grafik der Suche nach Kehrmaschine und Splitter.

Klicken Sie auf das Bild, um auf den Kurs zuzugreifen.

In der ersten Besetzung führt Jonathan in die Konzepte der Big-O-Notation und der binären Suche ein , den Algorithmus, mit dem wir arbeiten werden.

Die Big-O-Notation ist ein Mittel zur Beschreibung der Worst-Case-Leistung eines Algorithmus. Ein großes O von O (n) besagt, dass die Laufzeit proportional zu n ist, wenn ein Array eine Länge von n Elementen hat. Mit anderen Worten, ein Array von sieben Einträgen benötigt im schlimmsten Fall 7 Suchvorgänge, genauso wie ein Array von 7 Millionen Einträgen im schlimmsten Fall 7 Millionen Einträge benötigt. Wir können auch sagen, dass die Laufzeit dieses Algorithmus linear ist, wie in der obigen Grafik dargestellt.

Die binäre Suche ist eine von mehreren Strategien zur Beantwortung der Frage "Wo erscheint dieses Element in einer Liste?"

Bei der Beantwortung der Frage gibt es zwei Hauptansätze:

  • Kehrmaschine : Überprüfen Sie jedes Element in der Liste, bis das richtige Element gefunden wurde.
  • Splitter- / Binärsuche : Teilen Sie die Liste in zwei Hälften, prüfen Sie, ob Sie zu weit oder nicht weit genug gegangen sind, um das Objekt zu finden, suchen Sie entweder rechts oder links und wiederholen Sie den Vorgang, bis das Objekt gefunden ist.

Wir können uns diese Ansätze vorstellen, indem wir ein Telefonbuch der alten Schule überprüfen. Der Sweeper-Ansatz würde beinhalten, jeden einzelnen Eintrag von Anfang an durchzusehen, bis der richtige gefunden ist. Der Splitter-Ansatz wird von den meisten Menschen verwendet. Öffnen Sie das Buch nach dem Zufallsprinzip und prüfen Sie, ob Sie vorwärts oder rückwärts gehen müssen, bis sich der Eintrag befindet.

Die binäre Suche ist effizienter als der Sweeper-Ansatz, insbesondere bei größeren Listen. Dies funktioniert jedoch nur, wenn die Liste bereits sortiert wurde.

Während der Sweeper-Ansatz eine lineare Laufzeit (siehe Grafik oben) und ein Big O von O (n) hat, hat der Splitter-Ansatz eine sublineare Laufzeit und ein Big O von O (log n).

Imperativ

In der ersten Herausforderungsbesetzung ermutigt Jonathan uns, uns die Hände schmutzig zu machen, indem er die binäre Suche in einem traditionellen Stil implementiert, dh mit einem großen O von O (n), wobei eine feste Menge an Speicher und Schleifen verwendet wird.

Jonathan stellt uns eine Testsuite zur Verfügung, mit der wir sicherstellen können, dass unsere Lösung erfolgreich ist, und ermutigt uns, die Herausforderung selbst zu versuchen, bevor wir seine Implementierung überprüfen. Keine Spoiler hier, also gehen Sie zu den Darstellern, um es selbst zu versuchen.

Obwohl diese Lösung kurz ist und der ursprünglichen Formulierung der binären Suche nahe kommt, haben Sie wahrscheinlich bemerkt, dass die Lösung schwer zu schreiben war und aus Sicht der Software-Handwerkskunst nicht die beste Lösung. Lesen Sie weiter, um herauszufinden, wie Sie die Lösung verbessern können ...

Rekursion

In dieser Besetzung versuchen wir, unsere binäre Suche zu verbessern, indem wir eine neue Version mit einigen Einschränkungen implementieren. Während unsere Lösung immer noch ein großes O von O (n) haben sollte, sollte sie keine Schleifen verwenden und muss eine Rekursion verwenden. Alle Variablen sollten mit dem constOperator initialisiert werden, damit sie nicht mutiert werden können.

Jonanthan startet uns mit einer Skelettversion der Lösung und ermutigt uns dann, die Herausforderung selbst zu versuchen:

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

Wenn Sie diese Herausforderung abgeschlossen haben, haben Sie wahrscheinlich gesehen, dass diese Lösung viel einfacher zu lesen ist, aber ziemlich ausführlich. Im schlimmsten Fall kann es auch zu einer unendlichen Rekursion kommen. Fahren Sie mit dem Kurs fort, um festzustellen, ob es Möglichkeiten gibt, die Lösung zu optimieren ...

Schwanzrekursion

Die Herausforderung für die nächste Besetzung besteht darin, unsere vorherige Implementierung zu verbessern, indem Doppelarbeit reduziert wird.

Jonathan warnt uns davor, dass die Lösung schlechter aussehen wird als die beiden vorherigen Lösungen, bereitet uns jedoch auf einige bessere Optimierungen vor. Gehen Sie jetzt zum Kurs, um die Herausforderung selbst auszuprobieren und Jonathans Lösung zu sehen.

Array-Aufteilung

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.

Gehen Sie jetzt zum Kurs und probieren Sie die Herausforderung selbst aus. Wie Jonathan betont, ist diese Herausforderung schwierig, daher ist es in Ordnung, zu seiner Lösung zu springen, wenn Sie zu lange stecken bleiben, es aber zuerst selbst versuchen.

Einpacken

Du hast es bis zum Ende des Kurses geschafft - großartige Arbeit! Wir haben verschiedene Ansätze für die binäre Suche behandelt, die alle ihre eigenen Vor- und Nachteile haben, und wir haben ein großartiges Muskelgedächtnis aufgebaut, um effektiv mit Algorithmen arbeiten zu können.

Nachdem Sie sechs verschiedene Ansätze für die binäre Suche gesehen haben, werden Sie wahrscheinlich feststellen, dass sie an vielen verschiedenen Stellen in der Programmierung auftauchen.

Jonathans vollständiger Kurs mit 10 Algorithmen wird Ende des Jahres erscheinen, aber in der Zwischenzeit hoffe ich, dass Sie Ihre neu entdeckten binären Suchfähigkeiten sinnvoll einsetzen können.

Viel Spaß beim Codieren :)