Algoritmusok a Javascriptben - bináris keresés magyarázata

Ha új problémamegoldó készségeket szeretne szerezni, és szintet akar adni a számítástechnika ismereteihez, ne keresse tovább a Scrimba ingyenes egyórás tanfolyamát, a The Working Developer's Guide to Algorithms című cikket. Azok számára készült, akik nem rendelkeznek informatikai háttérrel, és úgy érzik, hogy hasznukra válna az algoritmikus gondolkodás megtanulása.

Mit csinál a tanfolyam?

Útmutatónk bemutatja, hogyan készíthet hat különböző bináris keresési algoritmust. A klasszikus Scrimba stílusban egy csomó kihívást tartalmaz útközben, így megszerezheti azt az izommemóriát, amelyre fejlesztenie kell a szoftverfejlesztő képességeit, és jobban működhet a jövőbeli algoritmusokkal.

Megtudhatja:

  • Bináris keresés
  • Nagy O jelölés
  • Kötelező kód
  • Rekurzió
  • Farok rekurziója
  • Tömb felosztása
  • Tömb nézet
  • Partíció

Minden algoritmust három szakaszban tanítanak:

  • Áttekintés: Jonathan koncepcionálisan vezeti be az algoritmust.
  • Megvalósítás: Az algoritmus saját verzióinak elkészítésével piszkosítjuk a kezünket.
  • Megoldás: Jonathan összehasonlítás céljából megmutatja a megvalósítását.

Előfeltételek

A legtöbbet hozza ki ebből a kurzusból, ha jól ismeri a Javascript-et, és ideális esetben már fejlesztőként dolgozik, vagy Bootcamp végzett.

Ha még nem vagy ott, nézd meg a Scrimba nagyszerű ingyenes bemutatóit: Bevezetés a JavaScriptbe és Bevezetés az ES6 + -ba.

Bevezetés az oktatóhoz

Jonathan Lee Martin szoftverfejlesztő, internetes oktató, előadó és szerző. Írással, beszéddel, magával ragadó Bootcamp-okkal, műhelytalálkozókkal és online oktatóanyagokkal segít más fejlesztőknek elérni szakmai és személyes céljaikat.

Olyan ügyfelekkel, mint például a NASA és a HP, ő csak az a személy, aki végigvezeti Önt a tanulási úton. Tehát kezdjük!

Bináris keresés

A Sweeper vs Splitter keresések grafikonja.

Kattintson a képre a tanfolyam eléréséhez.

Az első szereposztásban Jonathan bemutatja a Big-O jelölés és a bináris keresés fogalmát , azt az algoritmust, amellyel együtt fogunk dolgozni.

A Big-O jelölés az algoritmus legrosszabb eseteinek leírására szolgál. O (n) nagy O-je azt mondja, hogy ha egy tömbnek n eleme van, akkor a futási idő arányos lesz n-vel. Más szavakkal, a hét bejegyzésből álló tömb legrosszabb esetben 7 keresést fog végrehajtani, ugyanúgy, mint egy 7 millió bejegyzésből álló tömb 7 millió bejegyzést fog végezni a legrosszabb esetben. Azt is mondhatjuk, hogy az algoritmus futási ideje lineáris, amint azt a fenti grafikon szemlélteti.

A bináris keresés a "Hol jelenik meg ez az elem egy listában?" Kérdés megválaszolásának számos stratégiája.

A kérdés megválaszolásakor két fő megközelítés létezik:

  • Seprőgép : A lista minden elemének átnézése, amíg a megfelelő elem megtalálható.
  • Elosztó / bináris keresés : A lista felére osztása, annak ellenőrzése, hogy túl messzire ment-e vagy sem ahhoz, hogy megtalálja az elemet, a jobb vagy a bal oldalon történő keresés, és addig ismételje, amíg az elem meg nem jelenik.

Gondolhatunk ezekre a megközelítésekre egy régi iskola papír telefonkönyvének ellenőrzése szempontjából. A söpréses megközelítés magában foglalja az egyes bejegyzések áttekintését a kezdetektől a helyes megtalálásáig. A megosztó megközelítést alkalmazzák a legtöbben - véletlenszerűen kinyitja a könyvet, és megnézi, hogy előre vagy vissza kell-e haladnia, amíg a bejegyzés meg nem jelenik.

A bináris keresés hatékonyabb, mint a sweeper megközelítés, különösen nagyobb listák esetén. De csak akkor működik, ha a listát már rendezték.

Míg a sweeper megközelítésnek lineáris futási ideje van (lásd a fenti grafikont) és O (n) Big O-jának, addig a splitteres megközelítésnek sub-lineáris futási ideje és Big O-jának O (log n) van.

Parancsoló

Az első leadott kihívás során Jonathan arra ösztönöz minket, hogy piszkolódjunk be a bináris keresés hagyományos stílusú végrehajtásával, azaz O (n) nagy O-val, rögzített memória és hurkok felhasználásával.

Jonathan biztosít nekünk egy tesztcsomagot, amellyel biztosíthatjuk a megoldásunk eredményességét, és arra ösztönöz minket, hogy a megvalósítás ellenőrzése előtt próbáljuk ki magunkat a kihívással. Itt nincsenek spoilerek, ezért menjen át a stábhoz, hogy kipróbálja magát.

Bár ez a megoldás rövid és közel áll a bináris keresés eredeti megfogalmazásához, valószínűleg észrevette, hogy a megoldást nehéz volt megírni, és szoftveres kivitelezés szempontjából nem a legjobb megoldás. Olvassa el, hogy megtudja a megoldás szintjének emelésének módját ...

Rekurzió

Ebben a szereplőgárdában a bináris keresés fejlesztését vizsgáljuk egy új, néhány korlátozással rendelkező verzió bevezetésével. Míg a megoldásunknak továbbra is O-nak (O) nagy O-nak kell lennie, nem szabad hurokokat használnia, és rekurziót kell használnia. Minden változót inicializálni kell az constoperátorral, hogy ne legyenek mutálhatók.

Jonanthan elindít minket a megoldás csontváz változatával, majd arra bátorít, hogy próbáljuk ki egyedül a kihívást:

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

Ha teljesítette ezt a kihívást, valószínűleg látta, hogy ez a megoldás sokkal könnyebben olvasható, de meglehetősen részletes. A legrosszabb esetben ez is végtelen rekurziót eredményezhet. Folytassa a tanfolyammal, hogy lássa, van-e lehetőség a megoldás ésszerűsítésére ...

Farok rekurzió

A következő szereplők számára az a kihívás, hogy javítsuk korábbi megvalósításunkat a duplikációk csökkentésével.

Jonathan arra figyelmeztet minket, hogy a megoldás rosszabbul fog kinézni, mint az előző két megoldás, ugyanakkor jobb optimalizálásokra késztet bennünket a sorban. Most térjen át a tanfolyamra, hogy kipróbálja maga a kihívást, és lássa Jonathan megoldását.

Tömb felosztása

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.

Most térjen át a tanfolyamra, hogy kipróbálja maga a kihívást. Ahogy Jonathan rámutat, ez a kihívás trükkös, ezért rendben van átugrani a megoldását, ha túl sokáig elakad, de először egyedül adja meg.

Összecsomagolás

A tanfolyam végére értél - nagyszerű munka! A bináris keresés számos megközelítését áttekintettük, mindegyiknek megvannak a maga előnyei és hátrányai, és nagyszerű izommemóriát építettünk az algoritmusokkal való hatékony együttműködéshez.

Most, hogy látott hat különböző megközelítést a bináris kereséshez, valószínűleg észreveszi, hogy a programozás sok helyén felbukkan.

Jonathan teljes tanfolyama, amely 10 algoritmust tartalmaz, az év végén megjelenik, de addig is remélem, hogy jó hasznát veheti újdonsült bináris keresési képességeinek.

Boldog kódolás :)