streamalism.org

1. Áttekintés

Ebben a cikkben kitérünk a bináris keresés előnyeire az egyszerű lineáris kereséssel szemben, és áttekintjük annak Java-ban történő megvalósítását.

2. A hatékony keresés szükségessége

Tegyük fel, hogy a borértékesítéssel foglalkozunk, és naponta vevők milliói keresik fel alkalmazásunkat.

Az alkalmazásunk révén az ügyfél kiszűrheti azokat az elemeket, amelyek ára alacsonyabb n dollárt, válasszon ki egy üveget a keresési eredmények közül, és tegye a kosarába. Több millió felhasználónk keresi a borokat másodpercenként árkorlátozással. Az eredményeknek gyorsaknak kell lenniük.

A háttérlapon algoritmusunk lineáris keresést végez a teljes borlistán, összehasonlítva az ügyfél által megadott árkorlátot a listában szereplő minden borosüveg árával.

Ezután olyan elemeket ad vissza, amelyek ára alacsonyabb vagy egyenlő az árkorláttal. Ennek a lineáris keresésnek az idő bonyolultsága Tovább).

Ez azt jelenti, hogy minél nagyobb a palackok száma a rendszerünkben, annál több időbe telik. A keresési idő a bevezetett új elemek számával arányosan növekszik.

Ha rendezni kezdjük az elemeket rendezett sorrendben, és elemeket keresünk a bináris keresés segítségével, akkor elérhetjük a komplexitását O (log n).

A bináris keresés során a keresési eredmények által elvárt idő természetesen nő az adatkészlet méretével, de nem arányosan.

3. Bináris keresés

Egyszerűen fogalmazva, az algoritmus összehasonlítja a kulcs érték a tömb középső elemével; ha egyenlőtlenek, akkor megszűnik az a fele, amelyben a kulcs nem lehet része, és a fennmaradó felét a sikerig folytatja.

Ne feledje - a legfontosabb szempont itt az, hogy a tömb már rendezve van.

Ha a keresés azzal ér véget, hogy a fennmaradó fele üres, a kulcs nincs a tömbben.

3.1. Iteratív impl

public int runBinarySearchIterative (int [] sortedArray, int kulcs, int alacsony, int magas) {int index = Egész.MAX_VALUE; míg (alacsony <= magas) {int közepes = (alacsony + magas) / 2; if (sortedArray [középső] kulcs) {magas = közepe - 1; } else if (sortedArray [mid] == kulcs) {index = mid; szünet; }} visszatérési index; }

A runBinarySearchIterative módszer a sortedArray, kulcs & a alacsony & magas indexei a sortedArray mint érvek. A módszer első futtatásakor a alacsony, az első indexe sortedArray, értéke 0, míg a magas, a sortedArray, megegyezik a hosszával - 1.

A középső a középső indexe sortedArray. Most az algoritmus fut a míg hurok a kulcs a középső index tömbértékével sortedArray.

3.2. Rekurzív impl

Most nézzünk meg egy egyszerű, rekurzív megvalósítást is:

public int runBinarySearchRecursively (int [] sortedArray, int kulcs, int alacsony, int magas) {int közép = (alacsony + magas) / 2; ha (magas <alacsony) {visszatérés -1; } if (kulcs == sortedArray [középső]) {visszatér középen; } else if (kulcs <sortedArray [középső]) {return runBinarySearchRecursively (sortedArray, kulcs, alacsony, középső - 1); } else {return runBinarySearchRecursively (sortedArray, kulcs, középső + 1, magas); }} 

A runBinarySearchRecursively módszer elfogadja a sortedArray, kulcs, a alacsony és magas indexei sortedArray.

3.3. Használata Tömbök.binarySearch ()

int index = Tömbök.binarySearch (sortedArray, kulcs); 

Egy sorted Array és egy intkulcs, amelyet egész számok tömbjében kell keresni, argumentumként továbbítják a binarySearch módszer a Java Tömbök osztály.

3.4. Használata Gyűjtemények.binarySearch ()

int index = Collections.binarySearch (sortedList, kulcs); 

Egy rendezett lista & an Egész számkulcs, amelyet meg kell keresni a Egész szám objektumokat, argumentumként továbbítják a binarySearch módszer a Java Gyűjtemények osztály.

3.5. Teljesítmény

Az, hogy rekurzív vagy iteratív megközelítést alkalmazunk az algoritmus megírásához, többnyire személyes preferenciák kérdése. De mégis itt van néhány pont, amelyekkel tisztában kell lennünk:

1. A rekurzió lassabb lehet az a fenntartásának rezsije miatt Kazal és általában több memóriát foglal el

2. A rekurzió nem Kazal-barátságos. Okozhatja StackOverflowException nagy adatkészletek feldolgozásakor

3. A rekurzió egyértelműbbé teszi a kódot, mivel rövidebbé teszi az iteratív megközelítéshez képest

Ideális esetben egy bináris keresés kevesebb összehasonlítást hajt végre, szemben az n nagy értékek lineáris keresésével. Kisebb n érték esetén a lineáris keresés jobban teljesíthet, mint egy bináris keresés.

Tudni kell, hogy ez az elemzés elméleti, és a kontextustól függően változhat.

Is, a bináris keresési algoritmusnak rendezett adathalmazra van szüksége, amelynek költségei is vannak. Ha az adatok rendezéséhez egyesítési rendezési algoritmust használunk, akkor a n log n bekerül a kódunkba.

Tehát először jól elemeznünk kell a követelményeinket, majd döntenünk kell arról, hogy mely keresési algoritmus felel meg a legjobban az igényeinknek.

4. Következtetés

Ez az oktatóanyag bináris keresési algoritmus megvalósítását és olyan forgatókönyvet mutatott be, ahol lineáris keresés helyett előnyösebb lenne használni.

Kérjük, keresse meg az oktatóanyag kódját a GitHubon.