Algoritmi u Javascriptu - objašnjeno binarno pretraživanje

Ako želite steći nove vještine rješavanja problema i povisiti svoje znanje iz računalnih znanosti, ne tražite dalje od Scrimbinog besplatnog jednosatnog tečaja, Vodič za algoritme radnog programera. Dizajniran je za one koji nemaju predznanje iz računalnih znanosti i smatraju da bi im koristilo učenje algoritamskog razmišljanja.

Što tečaj radi?

Naš vodič vodi vas kroz izradu šest različitih algoritama binarnog pretraživanja. U klasičnom Scrimba stilu sadrži hrpu izazova na putu, tako da ćete steći memoriju mišića koja vam je potrebna da biste poboljšali svoje vještine programera i bolje radili s algoritmima.

Naučit ćete:

  • Binarno pretraživanje
  • Veliki O zapis
  • Imperativni kod
  • Rekurzija
  • Rekurzija repa
  • Dijeljenje niza
  • Prikaz niza
  • Pregrada

Svaki se algoritam podučava u tri faze:

  • Prolazak kroz korak: Jonathan konceptualno uvodi algoritam.
  • Implementacija: Prljamo ruke izradom vlastitih verzija algoritma.
  • Rješenje: Jonathan nam pokazuje svoju primjenu radi usporedbe.

Preduvjeti

Iz ovog ćete tečaja izvući maksimum ako dobro razumijete Javascript i ako idealno već radite kao programer ili ste diplomac Bootcampa.

Ako još niste tamo, pogledajte izvrsne besplatne vodiče Scrimbe Uvod u JavaScript i Uvod u ES6 +.

Uvod u instruktora

Jonathan Lee Martin je programer, web edukator, govornik i autor. Pomaže drugim programerima u postizanju njihovih profesionalnih i osobnih ciljeva pisanjem, govorom, impresivnim Bootcampovima, radionicama i mrežnim tutorialima.

S klijentima, uključujući tvrtke poput NASA-e i HP-a, on je samo osoba koja će vas provesti kroz put učenja. Pa krenimo!

Binarno pretraživanje

Grafikon pretraživanja Sweeper vs Splitter.

Kliknite sliku da biste pristupili tečaju.

U prvoj postavi Jonathan upoznaje koncepte Big-O notacije i binarnog pretraživanja , algoritam s kojim ćemo raditi.

Oznaka Big-O sredstvo je za opisivanje najgorih performansi algoritma. Veliki O od O (n) kaže da će, ako niz ima duljinu od n elemenata, vrijeme izvođenja biti proporcionalno n. Drugim riječima, niz od sedam unosa potrajat će 7 pretraživanja u najgorem slučaju, kao što će niz od 7 milijuna unosa uzeti 7 milijuna unosa u najgorem slučaju. Također možemo reći da je vrijeme izvođenja ovog algoritma linearno, kao što je prikazano na gornjem grafikonu.

Binarno pretraživanje jedna je od nekoliko strategija za odgovor na pitanje "Gdje se ovaj element pojavljuje na popisu?"

Prilikom odgovaranja na pitanje postoje dva glavna pristupa:

  • Pomet : Provjeravanje svake stavke na popisu dok se ne pronađe ispravna stavka.
  • Razdjelnik / binarno pretraživanje : dijeljenje popisa na pola, provjera da li ste otišli predaleko ili nedovoljno da biste pronašli stavku, pretražujući desnu ili lijevu stranu i ponavljajući dok se stavka ne pronađe.

Ove pristupe možemo zamisliti u smislu provjere telefonskog imenika iz stare škole. Pristup čistaču uključivao bi pregledavanje svakog unosa od početka do pronalaska ispravnog. Većina ljudi bi koristila splitter pristup - nasumično otvaranje knjige i provjeravanje trebate li ići naprijed ili natrag dok se ne pronađe unos.

Binarno pretraživanje učinkovitije je od čišćenja, posebno za veće popise. Ali to djeluje samo kad je popis već razvrstan.

Dok pristup metla ima linearno vrijeme izvođenja (vidi gornji grafikon) i Big O od O (n), splitter pristup ima sublinearno vrijeme izvođenja i veliki O od O (log n).

Imperativ

U prvom izazovu, Jonathan nas potiče da zaprljamo ruke primjenom binarnog pretraživanja u tradicionalnom stilu, to jest s velikim O od O (n), koristeći fiksnu količinu memorije i petlje.

Jonathan nam pruža testni paket koji možemo koristiti da bismo bili sigurni da je naše rješenje uspješno i potiče nas da sami isprobamo izazov prije provjere njegove primjene. Ovdje nema spojlera, zato krenite prema glumačkoj postavi i probajte sami.

Iako je ovo rješenje kratko i blisko izvornoj formulaciji binarnog pretraživanja, vjerojatno ste primijetili da je rješenje bilo teško napisati, a sa stanovišta izrade softvera nije najbolje rješenje. Pročitajte kako biste saznali načine za poravnanje rješenja ...

Rekurzija

U ovoj postavi gledamo na poboljšanje našeg binarnog pretraživanja primjenom nove verzije s nekoliko ograničenja. Iako bi naše rješenje još uvijek trebalo imati veliki O od O (n), ne bi trebalo koristiti petlje i mora koristiti rekurziju. Sve varijable treba inicijalizirati s constoperatorom kako ne bi mogle biti mutirane.

Jonanthan nas pokreće s skeletnom verzijom rješenja, a zatim nas potiče da sami isprobamo izazov:

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

Ako ste dovršili ovaj izazov, vjerojatno ste vidjeli da je ovo rješenje puno lakše čitati, ali prilično je opširno. U najgorem slučaju, to također može rezultirati beskonačnom rekurzijom. Nastavite s tečajem da biste vidjeli postoje li načini usmjeravanja rješenja ...

Rekurzija repa

Izazov za sljedeću glumačku postavu je poboljšati našu prethodnu implementaciju smanjenjem dupliciranja.

Jonathan nas upozorava da će rješenje izgledati gore od prethodna dva rješenja, međutim postavlja nas za neke bolje optimizacije dalje. Krenite sada na tečaj da biste sami isprobali izazov i vidjeli Jonathanovo rješenje.

Podjela niza

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.

Krenite sada na tečaj da biste sami isprobali izazov. Kao što Jonathan ističe, ovaj je izazov lukav, pa je u redu da prijeđete na njegovo rješenje ako predugo zapnete, ali pokušajte prvo sami.

Zamotati

Došli ste do kraja tečaja - sjajno! Pokrili smo nekoliko pristupa binarnom pretraživanju, sve s vlastitim prednostima i nedostacima, i izgradili smo sjajnu mišićnu memoriju za učinkovit rad s algoritmima.

Sad kad ste vidjeli šest različitih pristupa binarnom pretraživanju, vjerojatno ćete primijetiti da se pojavljuje na mnogo različitih mjesta u programiranju.

Jonathanov cjeloviti tečaj s 10 algoritama izaći će krajem godine, ali u međuvremenu se nadam da ćete svoje novootkrivene vještine binarnog pretraživanja dobro iskoristiti.

Sretno kodiranje :)