Skôr ako sa naučíme binárne vyhľadávanie, poďme sa naučiť:
Čo je to Search?
Vyhľadávanie je nástroj, ktorý umožňuje používateľovi vyhľadať dokumenty, súbory, médiá alebo akýkoľvek iný typ údajov uchovávaných v databáze. Vyhľadávanie funguje na jednoduchom princípe porovnania kritérií so záznamami a ich zobrazenia používateľovi. Týmto spôsobom funguje najzákladnejšia funkcia vyhľadávania.
Čo je to binárne vyhľadávanie?
Binárne vyhľadávanie je pokročilý typ vyhľadávacieho algoritmu, ktorý vyhľadáva a načítava údaje z triedeného zoznamu položiek. Jeho hlavný pracovný princíp spočíva v rozdelení údajov v zozname na polovicu, kým sa nenájde požadovaná hodnota a nezobrazí sa používateľovi vo výsledku vyhľadávania. Binárne vyhľadávanie je všeobecne známe ako hľadanie v polovičnom intervale alebo logaritmické vyhľadávanie .
V tomto výučbe algoritmu sa dozviete:
- Čo je to Search?
- Čo je to binárne vyhľadávanie?
- Ako funguje binárne vyhľadávanie?
- Príklad binárneho vyhľadávania
- Prečo potrebujeme binárne vyhľadávanie?
Ako funguje binárne vyhľadávanie?
Binárne vyhľadávanie funguje nasledujúcim spôsobom:
- Proces vyhľadávania sa spustí vyhľadaním stredného prvku zoradeného poľa údajov
- Potom sa kľúčová hodnota porovná s prvkom
- Ak je kľúčová hodnota menšia ako stredný prvok, potom vyhľadávanie analyzuje horné hodnoty so stredným prvkom na porovnanie a porovnanie
- V prípade, že je kľúčová hodnota väčšia ako stredný prvok, potom vyhľadávanie analyzuje nižšie hodnoty stredného prvku na porovnanie a porovnanie
Príklad binárneho vyhľadávania
Pozrime sa na príklad slovníka. Ak potrebujete nájsť určité slovo, nikto neprechádza po každom slove postupne, ale náhodne vyhľadá najbližšie slová, aby vyhľadal požadované slovo.
Obrázok vyššie zobrazuje nasledovné:
- Máte pole s 10 číslicami a prvok 59 je potrebné nájsť.
- Všetky prvky sú označené indexom od 0 do 9. Teraz sa počíta stred poľa. Ak to chcete urobiť, vezmete hodnoty indexu zľava a doprava a vydelíte ich 2. Výsledok je 4,5, ale vezmeme hodnotu minima. Preto je stred 4.
- Algoritmus vypustí všetky prvky zo strednej (4) na najnižšiu hranicu, pretože 59 je väčšie ako 24 a teraz v poli ostáva iba 5 prvkov.
- Teraz je 59 viac ako 45 a menej ako 63. Stred je 7. Pravá hodnota indexu sa preto stane strednou - 1, čo sa rovná 6, a ľavá hodnota indexu zostane rovnaká ako predtým, čo je 5.
- V tomto okamihu viete, že 59 prichádza po 45. Ľavý index, ktorý je 5, sa preto tiež stane stredom.
- Tieto iterácie pokračujú, kým sa pole nezredukuje iba na jeden prvok, alebo kým sa hľadaná položka nestane stredom poľa.
Príklad 2
Pozrime sa na nasledujúci príklad, aby sme pochopili fungovanie binárneho vyhľadávania
- Máte pole zoradených hodnôt od 2 do 20 a musíte nájsť 18.
- Priemer dolnej a hornej hranice je (l + r) / 2 = 4. Hľadaná hodnota je väčšia ako stredná hodnota, ktorá je 4.
- Hodnoty poľa menšie ako stredná sú z vyhľadávania vynechané a hodnoty väčšie ako stredná hodnota 4 sú prehľadávané.
- Toto je opakujúci sa proces delenia, kým sa nenájde skutočná položka, ktorá sa má prehľadať.
Prečo potrebujeme binárne vyhľadávanie?
Z nasledujúcich dôvodov je binárne vyhľadávanie lepšou voľbou na použitie ako vyhľadávací algoritmus:
- Binárne vyhľadávanie funguje efektívne na triedených dátach bez ohľadu na veľkosť dát
- Namiesto vykonávania vyhľadávania postupnosťou údajov v poradí, binárny algoritmus náhodne pristupuje k údajom, aby našiel požadovaný prvok. Vďaka tomu sú vyhľadávacie cykly kratšie a presnejšie.
- Binárne vyhľadávanie vykonáva porovnanie zoradených údajov na základe princípu usporiadania ako pri použití porovnania rovnosti, ktoré je pomalšie a väčšinou nepresné.
- Po každom cykle vyhľadávania algoritmus rozdelí veľkosť poľa na polovicu, takže v nasledujúcej iterácii bude fungovať iba vo zvyšnej polovici poľa.
Zhrnutie
- Vyhľadávanie je nástroj, ktorý umožňuje používateľovi vyhľadávať dokumenty, súbory a iné typy údajov. Binárne vyhľadávanie je pokročilý typ vyhľadávacieho algoritmu, ktorý vyhľadáva a načítava údaje z triedeného zoznamu položiek.
- Binárne vyhľadávanie je všeobecne známe ako hľadanie v polovičnom intervale alebo logaritmické vyhľadávanie
- Funguje to tak, že sa pole rozdelí na polovicu pri každej nájdenej iterácii pod požadovaným prvkom.
- Binárny algoritmus zaberá stred poľa vydelením súčtu hodnôt indexu vľavo a vpravo číslom 2. Teraz algoritmus zruší dolnú alebo hornú hranicu prvkov zo stredu poľa v závislosti od prvku, ktorý sa má nájsť. .
- Algoritmus náhodne pristupuje k údajom, aby našiel požadovaný prvok. Vďaka tomu sú vyhľadávacie cykly kratšie a presnejšie.
- Binárne vyhľadávanie vykonáva porovnanie zoradených údajov na základe princípu objednávania, než pri použití pomalého a nepresného porovnania rovnosti.
- Binárne vyhľadávanie nie je vhodné pre netriedené údaje.