Algoritmer i Javascript - Binær søgning forklaret

Hvis du vil få nye færdigheder til problemløsning og øge din datalogiske viden, skal du ikke lede længere end Scrimbas gratis en times kursus, The Working Developer's Guide To Algorithms. Det var designet til dem, der ikke har en baggrund inden for datalogi og føler, at de ville have gavn af at lære at tænke algoritmisk.

Hvad gør kurset?

Vores guide fører dig gennem, hvordan du opretter seks forskellige binære søgealgoritmer. I klassisk Scrimba-stil indeholder den en masse udfordringer undervejs, så du får den muskelhukommelse, du har brug for, for at forbedre dine færdigheder som softwareudvikler og arbejde bedre med algoritmer fremover.

Du lærer:

  • Binær søgning
  • Stor O notation
  • Imperativ kode
  • Rekursion
  • Hale rekursion
  • Array opdeling
  • Array visning
  • Skillevæg

Hver algoritme undervises i tre faser:

  • Gennemgang: Jonathan introducerer algoritmen konceptuelt.
  • Implementering: Vi får vores hænder beskidte ved at lave vores egne versioner af algoritmen.
  • Løsning: Jonathan viser os sin implementering til sammenligning.

Forudsætninger

Du får mest muligt ud af dette kursus, hvis du har en god forståelse af Javascript og ideelt set allerede arbejder som udvikler eller er Bootcamp-kandidat.

Hvis du ikke er der endnu, skal du tjekke Scrimbas fantastiske gratis tutorials Introduktion til JavaScript og Introduktion til ES6 +.

Introduktion til instruktøren

Jonathan Lee Martin er softwareudvikler, webpædagog, højttaler og forfatter. Han hjælper andre udviklere med at nå deres professionelle og personlige mål gennem skrivning, tale, fordybende Bootcamps, workshops og online tutorials.

Med kunder, herunder virksomheder som NASA og HP, er han bare den person, der fører dig gennem læringsrejsen. Så lad os komme i gang!

Binær søgning

Graf over Sweeper vs Splitter-søgninger.

Klik på billedet for at få adgang til kurset.

I den første rollebesætning introducerer Jonathan koncepterne Big-O notation og binær søgning , den algoritme, vi vil arbejde med.

Big-O-notation er et middel til at beskrive en algoritmes værste tilfælde. En stor O af O (n) siger, at hvis en matrix har en længde på n elementer, vil løbetiden være proportional med n. Med andre ord, en matrix med syv poster vil tage 7 opslag i værste fald, ligesom en matrix på 7 millioner poster vil tage 7 millioner poster i værste fald. Vi kan også sige, at denne algoritmes løbetid er lineær, som illustreret i grafen ovenfor.

Binær søgning er en af ​​flere strategier til besvarelse af spørgsmålet "Hvor vises dette element på en liste?"

Når du besvarer spørgsmålet, er der to hovedtilgange:

  • Fejemaskine : Gennemse hvert emne på listen, indtil det rigtige emne er fundet.
  • Splitter / binær søgning : Opdel listen i halvdelen, kontroller, om du er gået for langt eller ikke langt nok til at finde emnet, søge i henholdsvis højre eller venstre side og gentage, indtil varen er placeret.

Vi kan tænke på disse tilgange med hensyn til kontrol af en old-school papir telefonbog. Fejemetoden indebærer at kigge igennem hver eneste indgang fra starten, indtil den rigtige er placeret. Splitter-tilgangen er den, de fleste mennesker ville bruge - at åbne bogen tilfældigt og se, om du har brug for at gå frem eller tilbage, indtil posten er placeret.

Binær søgning er mere effektiv end fejemetoden, især for større lister. Men det fungerer kun, når listen allerede er sorteret.

Mens fejemetoden har en lineær køretid (se grafen ovenfor) og Big O af O (n), har splittermetoden en sublinear runtime og en Big O af O (log n).

Imperativt

I den første udfordring, opfordrer Jonathan os til at gøre vores hænder beskidte ved at implementere binær søgning i en traditionel stil, det vil sige med en stor O af O (n) ved hjælp af en fast mængde hukommelse og sløjfer.

Jonathan forsyner os med en testpakke, vi kan bruge til at sikre, at vores løsning er vellykket, og opfordrer os til selv at prøve udfordringen, før vi tjekker hans implementering. Ingen spoilere her, så gå over til rollebesætningen for at prøve det selv.

Mens denne løsning er kort og tæt på den oprindelige formulering af binær søgning, har du sandsynligvis bemærket, at løsningen var vanskelig at skrive og ikke den bedste løsning set fra et softwarehåndværk. Læs videre for at finde ud af måder at niveauere løsningen på ...

Rekursion

I denne rollebesætning ser vi på at forbedre vores binære søgning ved at implementere en ny version med nogle få begrænsninger. Mens vores løsning stadig skal have en stor O af O (n), skal den ikke bruge sløjfer og skal bruge rekursion. Alle variabler skal initialiseres med constoperatøren, så de ikke kan muteres.

Jonanthan starter os med en skeletversion af løsningen og opfordrer os derefter til at prøve udfordringen på egen hånd:

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

Hvis du har gennemført denne udfordring, har du sandsynligvis set, at denne løsning er meget nemmere at læse, men er ret detaljeret. I værste fald kan det også resultere i uendelig rekursion. Fortsæt med kurset for at se, om der er måder at strømline løsningen på ...

Hale rekursion

Udfordringen for den næste rollebesætning er at forbedre vores tidligere implementering ved at reducere dobbeltarbejde.

Jonathan advarer os om, at løsningen vil se dårligere ud end de to foregående løsninger, men den sætter os i stand til nogle bedre optimeringer længere nede på linjen. Gå over til kurset nu for at prøve udfordringen for dig selv og se Jonathan's løsning.

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.

Gå over til kurset nu for at prøve udfordringen selv. Som Jonathan påpeger, er denne udfordring vanskelig, så det er ok at springe til hans løsning, hvis du sidder fast for længe, ​​men giver det en chance først på egen hånd.

Afslutning

Du er nået til slutningen af ​​kurset - godt arbejde! Vi har dækket adskillige tilgange til binær søgning, alle med deres egne fordele og ulemper, og vi har bygget nogle gode muskelhukommelser til at arbejde effektivt med algoritmer.

Nu hvor du har set seks forskellige tilgange til binær søgning, vil du sandsynligvis bemærke, at det dukker op mange forskellige steder i programmeringen.

Jonatans fulde kursus med 10 algoritmer vil komme ud i slutningen af ​​året, men i mellemtiden håber jeg, du kan bruge dine nyfundne binære søgefærdigheder til god brug.

Glad kodning :)