Algoritmid Javascriptis - binaarotsing selgitatud

Kui soovite omandada uusi probleemide lahendamise oskusi ja täiendada oma arvutiteaduse alaseid teadmisi, siis ärge vaadake muud kui Scrimba tasuta ühetunnist kursust The Working Developer's Guide to Algorithms. See oli mõeldud neile, kellel pole arvutiteaduse tausta ja kes tunnevad, et neile oleks kasulik õppida algoritmiliselt mõtlema.

Mida kursus teeb?

Meie juhend tutvustab teid kuue erineva binaarse otsingu algoritmi loomise kaudu. Klassikalises Scrimba stiilis sisaldab see tervet rida väljakutseid, nii et saate lihasmälu, mida on vaja tarkvaraarendaja oskuste parandamiseks, ja töötate paremini algoritmidega edasi.

Sa õpid:

  • Binaarotsing
  • Suur O tähis
  • Kohustuslik kood
  • Rekursioon
  • Saba rekursioon
  • Massiivi jagamine
  • Massiivivaade
  • Jaotus

Iga algoritmi õpetatakse kolmes etapis:

  • Läbikäik: Jonathan tutvustab algoritmi kontseptuaalselt.
  • Rakendamine: me määrime oma käed määrates algoritmi oma versioonid.
  • Lahendus: Jonathan näitab meile võrdluseks oma teostust.

Eeldused

Saate sellest kursusest maksimumi võtta, kui olete Javascriptist hästi aru saanud ja töötate ideaalis juba arendajana või olete Bootcampi lõpetanud.

Kui te pole veel seal, vaadake Scrimba suurepäraseid tasuta õpetusi Sissejuhatus JavaScripti ja ES6 + sissejuhatus.

Juhendaja tutvustus

Jonathan Lee Martin on tarkvaraarendaja, veebikoolitaja, esineja ja autor. Ta aitab teistel arendajatel oma tööalaseid ja isiklikke eesmärke saavutada kirjutamise, rääkimise, kaasahaaravate Bootcampide, töötubade ja veebipõhiste õpetuste abil.

Klientidega, kelle hulka kuuluvad sellised ettevõtted nagu NASA ja HP, on ta just inimene, kes teid õppereisile viib. Nii et alustame!

Binaarotsing

Graafik Sweeper vs Splitter otsingutest.

Kursusele pääsemiseks klõpsake pilti.

Esimeses koosseisus tutvustab Jonathan Big-O notatsiooni ja binaarotsingu mõisteid - algoritmi, millega me töötame.

Big-O tähistamine on viis kirjeldada algoritmi halvimat toimivust. O (n) suur O ütleb, et kui massiivi pikkus on n elementi, on tööaeg proportsionaalne n-ga. Teisisõnu, seitsmest kirjest koosnev massiiv võtab halvimal juhul 7 otsinguid, nagu ka 7 miljoni kirjega massiiv halvimal juhul 7 miljonit kirjet. Samuti võime öelda, et selle algoritmi käitusaeg on lineaarne, nagu on näidatud ülaltoodud graafikul.

Binaarotsing on üks paljudest strateegiatest, kuidas vastata küsimusele "Kus see element loendis ilmub?"

Küsimusele vastamisel on kaks peamist lähenemist:

  • Pühkija : loendi iga üksuse kontrollimine, kuni leitakse õige üksus.
  • Jaotaja / binaarotsing : loendi poolitamine, kontrollimine, kas olete üksuse leidmiseks liiga kaugele jõudnud või liiga kaugele jõudnud, otsimine vastavalt kas paremalt või vasakult ja kordamine, kuni üksus asub.

Nendele lähenemisviisidele võime mõelda vana kooli paberist telefoniraamatu kontrollimise osas. Pühkimismeetod hõlmab kõigi sissekannete vaatamist algusest peale, kuni õige asukoht leitakse. Jaotur on lähenemisviis, mida enamik inimesi kasutaks - raamatu juhuslik avamine ja vaatamine, kas peate kandma edasi või tagasi, kuni kirje asub.

Binaarotsing on efektiivsem kui pühkimismeetod, eriti suuremate loendite puhul. Kuid see töötab ainult siis, kui loend on juba sorteeritud.

Kui pühkimismeetodil on lineaarne tööaeg (vt ülaltoodud graafikut) ja O (n) suur O, siis jagaja lähenemisviisil on alamlineaarne ja O suur O (log n).

Kohustuslik

Esimeses väljakutses julgustab Jonathan meid määrduma, rakendades binaarotsingu traditsioonilises stiilis, see tähendab O (n) suure O-ga, kasutades fikseeritud kogust mälu ja silmuseid.

Jonathan annab meile testipaketi, mida saame kasutada meie lahenduse edukuse tagamiseks, ja julgustab meid proovima väljakutset ise enne tema rakenduse kontrollimist. Siin pole spoilereid, nii et minge näitlejate juurde, et proovida ennast.

Kuigi see lahendus on lühike ja lähedane binaarotsingu algsele sõnastusele, olete ilmselt märganud, et lahendust oli keeruline kirjutada ja see ei olnud tarkvara käsitöö seisukohast parim lahendus. Loe edasi, et leida võimalusi lahenduse taseme tõstmiseks ...

Rekursioon

Selles koosseisus vaatleme oma binaarotsingu täiustamist, rakendades mõne piiranguga uue versiooni. Kuigi meie lahendusel peaks endiselt olema O (n) suur O, ei tohiks see kasutada silmusid ja ta peab kasutama rekursiooni. Kõik muutujad tuleks koos constoperaatoriga initsialiseerida, et neid ei saaks muteerida.

Jonanthan alustab meid lahenduse skeleti versiooniga ja julgustab meid seejärel proovima väljakutset iseseisvalt:

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

Kui olete selle väljakutse täitnud, olete ilmselt näinud, et seda lahendust on palju lihtsam lugeda, kuid see on üsna sõnakas. Halvimal juhul võib see põhjustada ka lõpmatu rekursiooni. Jätkake kursusega, et näha, kas on võimalusi lahenduse sujuvamaks muutmiseks ...

Saba rekursioon

Järgmise näitlejate väljakutseks on parandada meie eelmist rakendust, vähendades dubleerimist.

Jonathan hoiatab meid, et lahendus näeb välja halvem kui kaks eelmist lahendust, kuid see seab meid paremaks optimeerimiseks. Minge kursusele, et proovida väljakutset ise ja näha Jonathani lahendust.

Massiivi jagamine

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.

Minge kursusele, et proovida väljakutset ise. Nagu Jonathan märgib, on see väljakutse keeruline, seega on ok, kui jätate tema lahenduse vahele, kui jääte liiga kauaks kinni, kuid annate sellele kõigepealt ise.

Tõmba otsad kokku

Olete kursuse lõpuni jõudnud - suurepärane töö! Oleme käsitlenud mitmeid binaarotsingu lähenemisviise, millel kõigil on oma eelised ja puudused, ning algoritmidega tõhusaks töötamiseks oleme loonud suurepärase lihasmälu.

Nüüd, kui olete näinud kuut erinevat lähenemist binaarotsingule, märkate seda tõenäoliselt programmeerimisel paljudes erinevates kohtades.

Jonathani täielik kursus, mis sisaldab kümmet algoritmi, ilmub aasta lõpus, kuid seniks loodan, et saate oma äsja leitud binaarse otsingu oskused hästi kasutada.

Head kodeerimist :)