Algoritmus binárneho vyhľadávania v jazyku Java

1. Prehľad

V tomto článku sa budeme venovať výhodám binárneho vyhľadávania oproti jednoduchému lineárnemu vyhľadávaniu a prejdeme si jeho implementáciu v Jave.

2. Potreba efektívneho vyhľadávania

Povedzme, že podnikáme v oblasti predaja vína a našu aplikáciu každý deň navštevujú milióny kupujúcich.

Prostredníctvom našej aplikácie môže zákazník filtrovať položky, ktoré majú nižšiu cenu n dolárov, vyberte fľašu z výsledkov vyhľadávania a vložte ich do svojho košíka. Máme milióny používateľov, ktorí vyhľadávajú vína s cenovým limitom každú sekundu. Výsledky musia byť rýchle.

Na konci servera náš algoritmus lineárne prehľadáva celý zoznam vín a porovnáva cenový limit zadaný zákazníkom s cenou každej fľaše vína v zozname.

Potom vráti položky, ktorých cena je nižšia alebo rovná cenovému limitu. Toto lineárne vyhľadávanie má časovú zložitosť O (n).

To znamená, že čím väčší je počet fliaš na víno v našom systéme, tým viac času to zaberie. Čas hľadania sa zvyšuje úmerne s počtom nových položiek.

Ak začneme ukladať položky v zoradenom poradí a vyhľadávať položky pomocou binárneho vyhľadávania, môžeme dosiahnuť zložitosť O (log n).

Pri binárnom vyhľadávaní sa čas potrebný na výsledky vyhľadávania prirodzene zvyšuje s veľkosťou množiny údajov, nie však úmerne.

3. Binárne vyhľadávanie

Jednoducho povedané, algoritmus porovnáva kľúč hodnota so stredným prvkom poľa; ak sú nerovnaké, polovica, ktorej kľúč nemôže byť súčasťou, je vylúčená a hľadanie zvyšnej polovice pokračuje, kým nebude úspešná.

Pamätajte - kľúčovým aspektom je, že pole je už zoradené.

Ak hľadanie končí tým, že zostávajúca polovica bude prázdna, kľúč nie je v poli.

3.1. Iteratívny impl

public int runBinarySearchIterativne (int [] triedeneArray, int key, int low, int high) {int index = Integer.MAX_VALUE; while (low <= high) {int mid = (low + high) / 2; if (triedenéArray [stredné] tlačidlo) {vysoké = stredné - 1; } else if (orderedArray [mid] == key) {index = mid; prestávka; }} návratový index; }

The runBinarySearchIteratívne metóda vyžaduje a triedené pole, kľúč & the nízka & vysoká indexy indexu triedené pole ako argumenty. Pri prvom spustení metódy nízka, prvý index indexu triedené pole, je 0, zatiaľ čo vysoká, posledný index triedené pole, sa rovná jeho dĺžke - 1.

The stredný je stredný index indexu triedené pole. Teraz algoritmus spustí a zatiaľ čo slučka porovnávajúca kľúč s hodnotou poľa stredného indexu triedené pole.

3.2. Rekurzívny impl

Poďme sa teraz tiež pozrieť na jednoduchú rekurzívnu implementáciu:

public int runBinarySearchRecursively (int [] SortArray, int key, int low, int high) {int middle = (low + high) / 2; if (high <low) {return -1; } if (key == sortArray [stred]) {návrat stred; } else if (key <SortArray [Middle]) {return runBinarySearchRecursively (SortArray, Key, Low, Middle - 1); } else {return runBinarySearchRecursively (orderedArray, key, middle + 1, high); }} 

The runBinarySearchRecursively metóda akceptuje a triedené pole, kľúč, the nízka a vysoká indexy indexu triedené pole.

3.3. Použitím Polia.binarySearch ()

int index = Arrays.binarySearch (sortArray, kľúč); 

Triedené pole a an intkľúč, ktoré sa majú prehľadať v poli celých čísel, sa odovzdajú ako argumenty do binarySearch metóda Java Polia trieda.

3.4. Použitím Zbierky.binarySearch ()

int index = Collections.binarySearch (triedený zoznam, kľúč); 

Zoradený zoznam & an Celé číslokľúč, ktorý sa má vyhľadať v zozname Celé číslo objekty, sú odovzdané ako argumenty do binarySearch metóda Java Zbierky trieda.

3.5. Výkon

To, či na napísanie algoritmu použiť rekurzívny alebo iteračný prístup, je väčšinou vecou osobných preferencií. Ale stále je tu niekoľko bodov, ktoré by sme si mali uvedomiť:

1. Rekurzia môže byť pomalšia v dôsledku réžie údržby a stoh a zvyčajne zaberie viac pamäte

2. Rekurzia nie je stoh-priateľský. Môže to spôsobiť StackOverflowException pri spracovaní súborov veľkých údajov

3. Rekurzia dodáva kódu jasnosť, pretože je kratší v porovnaní s iteračným prístupom

V ideálnom prípade bude binárne vyhľadávanie vykonávať menší počet porovnaní na rozdiel od lineárneho vyhľadávania veľkých hodnôt n. Pri menších hodnotách n by mohlo lineárne vyhľadávanie fungovať lepšie ako binárne vyhľadávanie.

Jeden by mal vedieť, že táto analýza je teoretická a môže sa líšiť v závislosti od kontextu.

Tiež binárny vyhľadávací algoritmus vyžaduje triedený súbor údajov, ktorý má aj svoje náklady. Ak na triedenie údajov použijeme algoritmus zlučovania a zlučovania, je to ďalšia zložitosť n prihlásiť n je pridaný do nášho kódu.

Najprv teda musíme dobre analyzovať naše požiadavky a potom sa rozhodnúť, ktorý vyhľadávací algoritmus by vyhovoval našim požiadavkám najlepšie.

4. Záver

Tento tutoriál demonštroval implementáciu binárneho vyhľadávacieho algoritmu a scenár, v ktorom by bolo vhodnejšie použiť ho namiesto lineárneho vyhľadávania.

Kód výučby nájdete na stránkach GitHub.