Predtým, ako pochopíme rozdiely medzi lineárnym a binárnym vyhľadávaním, mali by sme najprv samostatne poznať lineárne vyhľadávanie a binárne vyhľadávanie.
Čo je lineárne vyhľadávanie?
Lineárne vyhľadávanie je známe aj ako sekvenčné vyhľadávanie, ktoré jednoducho skenuje každý prvok naraz. Predpokladajme, že chceme hľadať prvok v poli alebo zozname; jednoducho vypočítame jeho dĺžku a neskočíme na žiadnu položku.
Zoberme si jednoduchý príklad.
Predpokladajme, že máme pole 10 prvkov, ako je znázornené na obrázku nižšie:
Vyššie uvedený obrázok zobrazuje pole typu znakov s 10 hodnotami. Ak chceme hľadať „E“, vyhľadávanie začína od 0thprvok a skenuje každý prvok, kým sa prvok, t. j. 'E' nenájde. Nemôžeme priamo skočiť z 0thprvok do 4thprvok, t.j. každý prvok sa skenuje jeden po druhom, kým sa prvok nenájde.
Zložitosť lineárneho vyhľadávania
Lineárne vyhľadávanie prehľadáva každý prvok jeden po druhom, kým sa prvok nenájde. Ak sa počet prvkov zvýši, zvýši sa aj počet prvkov, ktoré sa majú skenovať. Môžeme povedať, že čas potrebný na vyhľadávanie prvkov je úmerný počtu prvkov . Preto zložitosť v najhoršom prípade je O(n)
Čo je to binárne vyhľadávanie?
Binárne vyhľadávanie je vyhľadávanie, pri ktorom sa vypočíta stredný prvok, aby sa zistilo, či je menší alebo väčší ako prvok, ktorý sa má prehľadávať. Hlavnou výhodou použitia binárneho vyhľadávania je, že neskenuje každý prvok v zozname. Namiesto skenovania každého prvku vykoná vyhľadávanie do polovice zoznamu. Binárne vyhľadávanie teda trvá menej času na vyhľadanie prvku v porovnaní s lineárnym vyhľadávaním.
Ten jeden predpokladom binárneho vyhľadávania je, že pole by malo byť v zoradenom poradí, zatiaľ čo lineárne vyhľadávanie funguje na zoradené aj netriedené pole. Binárny vyhľadávací algoritmus je založený na technike rozdeľ a dobyj, čo znamená, že pole rozdelí rekurzívne.
Pri binárnom vyhľadávaní sa používajú tri prípady:
Prípad 1: údaje
Prípad 2: údaje>a[stred], potom vpravo=stred-1
Prípad 3: Data = a[mid] // prvok sa našiel
Vo vyššie uvedenom prípade „ a ' je názov poľa, stred je index prvku vypočítaný rekurzívne, údajov je prvok, ktorý sa má hľadať, vľavo označuje ľavý prvok poľa a správny označuje prvok, ktorý sa vyskytuje na pravej strane poľa.
Poďme pochopiť fungovanie binárneho vyhľadávania na príklade.
Predpokladajme, že máme pole veľkosti 10, ktoré je indexované od 0 do 9, ako je znázornené na obrázku nižšie:
Chceme vyhľadať 70 prvkov z vyššie uvedeného poľa.
Krok 1: Najprv vypočítame stredný prvok poľa. Berieme do úvahy dve premenné, t.j. ľavú a pravú. Na začiatku vľavo = 0 a vpravo = 9, ako je znázornené na obrázku nižšie:
Hodnotu stredného prvku možno vypočítať takto:
Preto mid = 4 a a[mid] = 50. Prvok, ktorý sa má vyhľadať, je 70, takže a[mid] sa nerovná údajom. Prípad 2 je splnený, t.j. dáta>a[stred].
Krok 2: Ak je údaj>a[stred], hodnota vľavo sa zvýši o stred+1, t.j. vľavo=stred+1. Hodnota stredu je 4, takže hodnota vľavo bude 5. Teraz máme podpole, ako je znázornené na obrázku nižšie:
Teraz je stredná hodnota vypočítaná pomocou vyššie uvedeného vzorca a hodnota strednej hodnoty bude 7. Teraz môže byť stredná hodnota vyjadrená ako:
Na vyššie uvedenom obrázku môžeme pozorovať, že a[mid]>dáta, takže opäť, v ďalšom kroku sa vypočíta hodnota stredu.
Krok 3: Ako [stred]>údaje sa hodnota práva zníži o polovicu 1. Hodnota mid je 7, takže hodnota right bude 6. Pole môže byť reprezentované ako:
Znova sa vypočíta hodnota stredu. Hodnoty vľavo a vpravo sú 5 a 6. Preto je hodnota stredu 5. Teraz môže byť stred reprezentovaný v poli, ako je uvedené nižšie:
Na obrázku vyššie môžeme pozorovať, že [stred]
Krok 4: Ako [v strede] Teraz sa hodnota stredu vypočíta znova pomocou vzorca, o ktorom sme už hovorili. Hodnoty vľavo a vpravo sú 6 a 6, takže hodnota stredu bude 6, ako je znázornené na obrázku nižšie: Na obrázku vyššie môžeme pozorovať, že a[stred]=údaje. Preto je vyhľadávanie dokončené a prvok je úspešne nájdený. Nasledujú rozdiely medzi lineárnym a binárnym vyhľadávaním: Popis Lineárne vyhľadávanie je vyhľadávanie, ktoré nájde prvok v zozname postupným vyhľadávaním prvku, kým sa prvok nenájde v zozname. Na druhej strane, binárne vyhľadávanie je vyhľadávanie, ktoré rekurzívne nájde stredný prvok v zozname, kým sa stredný prvok nezhoduje s hľadaným prvkom. Fungovanie oboch vyhľadávaní Lineárne vyhľadávanie spustí vyhľadávanie od prvého prvku a prehľadá jeden prvok po druhom bez preskočenia na ďalší prvok. Na druhej strane binárne vyhľadávanie rozdelí pole na polovicu výpočtom stredného prvku poľa. Implementácia Lineárne vyhľadávanie môže byť implementované na ľubovoľnej lineárnej dátovej štruktúre, ako je vektor, jednoducho prepojený zoznam, dvojito prepojený zoznam. Na rozdiel od toho môže byť binárne vyhľadávanie implementované na dátových štruktúrach s obojsmerným prechodom, t. j. prechodom dopredu a dozadu. Zložitosť Lineárne vyhľadávanie sa používa jednoducho, alebo môžeme povedať, že je menej zložité, pretože prvky pre lineárne vyhľadávanie môžu byť usporiadané v ľubovoľnom poradí, zatiaľ čo pri binárnom vyhľadávaní musia byť prvky usporiadané v určitom poradí. Zoradené prvky Prvky pre lineárne vyhľadávanie môžu byť usporiadané v náhodnom poradí. Pri lineárnom vyhľadávaní nie je povinné, aby boli prvky usporiadané v zoradenom poradí. Na druhej strane pri binárnom vyhľadávaní musia byť prvky usporiadané v zoradenom poradí. Môže byť usporiadaný v rastúcom alebo klesajúcom poradí a podľa toho sa zmení aj algoritmus. Keďže binárne vyhľadávanie používa triedené pole, je potrebné vložiť prvok na správne miesto. Naproti tomu lineárne vyhľadávanie nepotrebuje triedené pole, takže nový prvok možno jednoducho vložiť na koniec poľa. Prístup Lineárne vyhľadávanie používa na nájdenie prvku iteratívny prístup, preto je tiež známy ako sekvenčný prístup. Naproti tomu binárne vyhľadávanie vypočítava stredný prvok poľa, takže používa prístup rozdeľuj a panuj. Súbor údajov Lineárne vyhľadávanie nie je vhodné pre veľký súbor údajov. Ak chceme hľadať prvok, ktorý je posledným prvkom poľa, začne lineárne vyhľadávanie hľadať od prvého prvku a pokračuje až po posledný prvok, takže čas potrebný na vyhľadávanie prvku by bol veľký. Na druhej strane je binárne vyhľadávanie vhodné pre veľký súbor údajov, pretože trvá menej času. Rýchlosť Ak je súbor údajov pri lineárnom vyhľadávaní veľký, výpočtové náklady by boli vysoké a rýchlosť by sa spomalila. Ak je súbor údajov pri binárnom vyhľadávaní veľký, výpočtové náklady by boli nižšie v porovnaní s lineárnym vyhľadávaním a rýchlosť by sa zvýšila. Rozmery Lineárne vyhľadávanie možno použiť na jednorozmernom aj viacrozmernom poli, zatiaľ čo binárne vyhľadávanie možno implementovať iba na jednorozmernom poli. Efektívnosť Lineárne vyhľadávanie je menej efektívne, ak vezmeme do úvahy veľké súbory údajov. Binárne vyhľadávanie je efektívnejšie ako lineárne vyhľadávanie v prípade veľkých súborov údajov. Pozrime sa na rozdiely v tabuľkovej forme. 
Rozdiely medzi lineárnym a binárnym vyhľadávaním
dizajnové vzory java
Základ porovnávania Lineárne vyhľadávanie Binárne vyhľadávanie Definícia Lineárne vyhľadávanie začne hľadať od prvého prvku a porovnáva každý prvok s hľadaným prvkom, kým sa prvok nenájde. Nájde pozíciu hľadaného prvku nájdením stredného prvku poľa. Zoradené údaje Pri lineárnom vyhľadávaní nemusia byť prvky usporiadané v zoradenom poradí. Predpokladom pre binárne vyhľadávanie je, že prvky musia byť usporiadané v zoradenom poradí. Implementácia Lineárne vyhľadávanie môže byť implementované na ľubovoľnú lineárnu dátovú štruktúru, ako je pole, prepojený zoznam atď. Implementácia binárneho vyhľadávania je obmedzená, pretože môže byť implementovaná iba na tých dátových štruktúrach, ktoré majú obojsmerný prechod. Prístup Je založený na sekvenčnom prístupe. Je založený na prístupe rozdeľuj a panuj. Veľkosť Je vhodnejšie pre malé súbory údajov. Je vhodnejšie pre veľké súbory údajov. Efektívnosť Je to menej efektívne v prípade veľkých súborov údajov. Je to efektívnejšie v prípade veľkých súborov údajov. Najhorší prípad Pri lineárnom vyhľadávaní je najhorším scenárom nájdenia prvku O(n). Pri binárnom vyhľadávaní je najhorším scenárom nájdenia prvku O(log2n). Najlepší scenár Pri lineárnom vyhľadávaní je najlepším scenárom na nájdenie prvého prvku v zozname O(1). Pri binárnom vyhľadávaní je najlepším scenárom na nájdenie prvého prvku v zozname O(1). Rozmerové pole Môže byť implementovaný na jedno aj viacrozmerné pole. Môže byť implementovaný iba na viacrozmernom poli.