Dacă doriți să obțineți noi abilități de rezolvare a problemelor și să vă ridicați cunoștințele în domeniul informaticii, nu căutați mai departe de cursul gratuit de o oră Scrimba, Ghidul dezvoltatorului de lucru pentru algoritmi. A fost conceput pentru cei care nu au o experiență în informatică și simt că ar beneficia de învățarea de a gândi algoritmic.

Ce face cursul?

Ghidul nostru vă prezintă modul de elaborare a șase algoritmi de căutare binari diferiți. În stilul clasic Scrimba, acesta conține o grămadă de provocări pe parcurs, astfel încât veți câștiga memoria musculară de care aveți nevoie pentru a vă îmbunătăți abilitățile ca dezvoltator de software și pentru a lucra mai bine cu algoritmi în viitor.

Veți învăța:

  • Căutare binară
  • Notare O mare
  • Cod imperativ
  • Recursivitate
  • Recursivitatea cozii
  • Împărțirea matricei
  • Vedere matrice
  • Partiție

Fiecare algoritm este predat în trei etape:

  • Procedură: Jonathan introduce algoritmul conceptual.
  • Implementare: Ne murdărim mâinile realizând propriile noastre versiuni ale algoritmului.
  • Soluţie: Jonathan ne arată implementarea sa pentru comparație.

Condiții prealabile

Veți profita la maximum de acest curs dacă aveți o bună înțelegere a Javascript și, în mod ideal, lucrați deja ca dezvoltator sau sunteți absolvent al Bootcamp.

Dacă nu sunteți încă acolo, consultați tutorialele gratuite gratuite ale Scrimba Introducere în JavaScript și Introducere în ES6 +.

Introducere la instructor

Jonathan Lee Martin este dezvoltator de software, educator web, vorbitor și autor. El îi ajută pe alți dezvoltatori să își atingă obiectivele profesionale și personale prin scris, vorbit, Bootcamp-uri captivante, ateliere și tutoriale online.

Cu clienți, inclusiv companii precum NASA și HP, el este doar persoana care vă va duce în călătoria de învățare. Deci sa începem!

Căutare binară

Graficul căutărilor Sweeper vs Splitter.
Faceți clic pe imagine pentru a accesa cursul.

În prima distribuție, Jonathan introduce conceptele de Notare Big-O și căutare binară, algoritmul cu care vom lucra.

Notare Big-O este un mijloc de a descrie cea mai slabă performanță a unui algoritm. Un Big O of O (n) spune că, dacă o matrice are o lungime de n elemente, timpul de rulare va fi proporțional cu n. Cu alte cuvinte, o matrice de șapte intrări va efectua 7 căutări în cel mai rău caz, la fel cum o matrice de 7 milioane de intrări va lua 7 milioane de intrări în cel mai rău caz. Putem spune, de asemenea, că timpul de execuție al acestui algoritm este liniar, așa cum se ilustrează în graficul de mai sus.

Căutare binară este una dintre mai multe strategii pentru a răspunde la întrebarea „Unde apare acest element într-o listă?”

Când răspundeți la întrebare, există două abordări principale:

  • Măturătoare: Verificarea fiecărui element din listă până la găsirea elementului corect.
  • Splitter / Căutare binară: Împărțirea listei în jumătate, verificarea dacă ați mers prea departe sau nu suficient de departe pentru a localiza elementul, căutând fie partea dreaptă, fie respectiv stânga și repetând până când elementul este localizat.

Ne putem gândi la aceste abordări în ceea ce privește verificarea unei cărți telefonice din hârtie veche. Abordarea măturătorului ar implica examinarea fiecărei intrări de la început până la localizarea celei corecte. Abordarea prin divizare este cea pe care ar folosi-o majoritatea oamenilor – deschiderea cărții la întâmplare și verificarea dacă trebuie să mergeți înainte sau înapoi până când intrarea este localizată.

Căutarea binară este mai eficientă decât abordarea maturatorului, în special pentru listele mai mari. Dar funcționează numai atunci când lista a fost deja sortată.

În timp ce abordarea măturătorului are un timp de execuție liniar (a se vedea graficul de mai sus) și O mare de O (n), abordarea prin separator are un timp de execuție sub-liniar și un O mare de O (log n).

Imperativ

În prima distribuție provocatoare, Jonathan ne încurajează să ne murdărim mâinile prin implementarea căutării binare într-un stil tradițional, adică cu un O mare de O (n), folosind o cantitate fixă ​​de memorie și bucle.

Jonathan ne oferă o suită de testare pe care o putem folosi pentru a ne asigura că soluția noastră are succes și ne încurajează să încercăm noi înșine provocarea înainte de a verifica implementarea sa. Nu există spoilere aici, așa că mergeți la distribuție pentru a încerca singur.

În timp ce această soluție este scurtă și aproape de formularea inițială de căutare binară, probabil ați observat că soluția a fost dificil de scris și nu cea mai bună soluție din punct de vedere al artizanatului software. Citiți mai departe pentru a afla modalități de a ridica nivelul soluției …

Recursivitate

În această distribuție, ne uităm la îmbunătățirea căutării noastre binare prin implementarea unei noi versiuni cu câteva constrângeri. Deși soluția noastră ar trebui să aibă în continuare un O mare de O (n), nu ar trebui să utilizeze bucle și trebuie să utilizeze recursivitate. Toate variabilele ar trebui inițializate cu const operator, astfel încât să nu poată fi mutate.

Jonanthan ne dă startul cu o versiune scheletică a soluției și apoi ne încurajează să încercăm singuri provocarea:

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

export default binarySearchWithRecursion;

Dacă ați finalizat această provocare, probabil ați văzut că această soluție este mult mai ușor de citit, dar este destul de detaliată. În cel mai rău caz, poate duce și la recursivitate infinită. Continuați cursul pentru a vedea dacă există modalități de eficientizare a soluției …

Recursiunea cozii

Provocarea pentru următoarea distribuție este de a îmbunătăți implementarea noastră anterioară prin reducerea duplicării.

Jonathan ne avertizează că soluția va arăta mai rău decât cele două soluții anterioare, cu toate acestea, ne pregătește pentru unele optimizări mai bune mai jos. Mergeți la curs acum pentru a încerca provocarea pentru dvs. și pentru a vedea soluția lui Jonathan.

Array Splitting

Dacă ați finalizat provocarea anterioară, este posibil să fi simțit că transmitem încă multe informații suplimentare în căutarea noastră binară prin recursivitate. Această distribuție se uită la un mod de curățare numit așa divizarea matricei.

Ne putem gândi la împărțirea matricei în termeni de exemplu din agenda noastră telefonică de mai devreme – ori de câte ori decidem că jumătate din agenda telefonică este irelevantă, o rupem și o aruncăm. În mod similar, următoarea noastră soluție ar trebui să ignore toate părțile din matrice care nu includ intrarea noastră dorită.

Pentru a ne ajuta să realizăm acest lucru, Jonathan ne începe cu un cod de schelet:

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

Apoi, ca de obicei, ne dă frâu liber pentru a încerca soluția pentru noi înșine înainte de a ne ghida prin propria sa implementare.

Deși aceasta este o metodă elegantă de căutare binară, deoarece implică realizarea unei copii a unei părți din matrice, nu mai are un O mare de O (n) și are o utilizare mai mare a memoriei și un timp de rulare mai lent. Continuați cursul pentru a afla dacă există o modalitate de a recâștiga o performanță mai mare cu o soluție de cod similară …

Array View

În această distribuție, căutăm modalități de îmbinare a performanțelor superioare ale soluțiilor noastre anterioare cu eleganța divizării matrice. Pentru a face acest lucru, creăm un obiect de tip matrice care răspunde la aceleași metode ca un tablou. Vom injecta apoi acest obiect în locul matricei originale.

Jonathan ne face să începem inițializând o funcție ArrayView care returnează un obiect care așteaptă trei argumente: array, start și end. Când este invocat, ArrayView ar trebui să returneze un obiect cu patru metode, length, toArray, slice și 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)

Provocarea noastră este să implementăm slice și get metode de ArrayView fără a face o copie a matricei originale. Faceți clic pentru a încerca și apoi vizualizați pasajul lui Jonathan.

Deși această soluție produce un cod mai bun, mai lizibil, este mai lungă decât unele dintre soluțiile noastre anterioare. Continuați cursul pentru a afla dacă putem păstra beneficiile ArrayView ridicând în același timp și mai mult din logica codului de căutare binar …

Partiție matrice

În ultima provocare turnată desigur, Jonathan ne oferă un scop de a extrage o parte din logica de recuperare criptică din versiunea noastră anterioară într-o structură de date.

Pentru aceasta, avem nevoie de o structură simplă de date care returnează partea din mijloc, stânga sau dreapta a unui tablou. Pentru a ne începe, Jonathan instalează o funcție ArrayPartition:

export let ArrayPartition = (array, pivot) => ({
	left: () => array.slice(0, pivot),
	middle: () => array.get(pivot),
	right: () => array.slice(pivot + 1, array.length),
});

Apoi, Jonathan configurează o nouă versiune de căutare binară numită binarySearchWithPartition, care are o semnătură de pornire la fel ca 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);

Provocarea noastră acum este să rescriem binarySearchWithPartition cu niciunul dintre bounce logică evidențiată mai sus, în loc să creeze o partiție matrice și să efectueze apeluri către metodele sale din stânga, mijloc și dreapta.

Mergeți acum la curs pentru a încerca singură provocarea. După cum subliniază Jonathan, această provocare este dificilă, deci este bine să treceți la soluția sa dacă rămâneți blocat prea mult timp, dar dați o încercare mai întâi pe cont propriu.

Învelire

Ați ajuns la sfârșitul cursului – muncă grozavă! Am acoperit mai multe abordări ale căutării binare, toate cu propriile avantaje și dezavantaje și am construit o memorie musculară excelentă pentru a lucra eficient cu algoritmi.

Acum că ați văzut șase abordări diferite ale căutării binare, probabil că veți observa că apare în multe locuri diferite din programare.

Cursul complet al lui Jonathan cu 10 algoritmi va fi publicat la sfârșitul anului, dar între timp, sper să vă puteți folosi abilitățile de căutare binară recent descoperite.

Codificare fericita 🙂