Hlavný rozdiel medzi lineárnym vyhľadávaním a binárnym vyhľadávaním spočíva v tom, že binárne vyhľadávanie trvá menej času na vyhľadanie prvku z triedeného zoznamu prvkov. Z toho vyplýva, že efektívnosť metódy binárneho vyhľadávania je väčšia ako lineárne vyhľadávanie.
Ďalším rozdielom medzi týmito dvomi je, že existuje predpoklad pre binárne vyhľadávanie, tj prvky musia byť triedené, zatiaľ čo v lineárnom vyhľadávaní neexistuje takýto predpoklad. Hoci obe vyhľadávacie metódy používajú rôzne techniky, ktoré sú uvedené nižšie.
Porovnávacia tabuľka
| Základ pre porovnanie | Lineárne vyhľadávanie | Binárne vyhľadávanie |
|---|---|---|
| Časová zložitosť | O (N) | O (log 2 N) |
| Najlepší čas | Prvý prvok O (1) | Stredový prvok O (1) |
| Predpoklad pre pole | Nie je potrebné | Array musí byť v triedenom poradí |
| Najhorší prípad pre počet prvkov N | N porovnania sú potrebné | Dokáže sa uzavrieť iba po 2 N porovnaní log |
| Možno implementovať na | Pole a prepojený zoznam | Nemôže byť priamo implementovaný na prepojenom zozname |
| Vložiť operáciu | Jednoducho vložte na konci zoznamu | Vyžadovať spracovanie na vloženie na jeho správnom mieste, aby ste udržiavali triedený zoznam. |
| Typ algoritmu | Iteračné v prírode | Rozdeľte a podmanite si v prírode |
| užitočnosť | Jednoduché použitie a nie je potrebné žiadne objednané prvky. | V každom prípade zložitý algoritmus a prvky by mali byť usporiadané v poriadku. |
| Riadky kódu | menej | viac |
Definícia lineárneho vyhľadávania
Pri lineárnom vyhľadávaní sa každý prvok poľa získava jeden po druhom v logickom poradí a kontroluje, či ide o požadovaný prvok alebo nie. Vyhľadávanie bude neúspešné, ak budú prístupné všetky prvky a požadovaný prvok sa nenašiel. V najhoršom prípade by sme museli skenovať polovicu veľkosti poľa (n / 2).
Preto môže byť lineárne vyhľadávanie definované ako technika, ktorá postupne prechádza po poli za účelom nájdenia danej položky. Program uvedený nižšie ilustruje vyhľadávanie prvku poľa pomocou vyhľadávania.
Účinnosť lineárneho vyhľadávania
Časová spotreba alebo počet porovnaní vykonaných pri vyhľadávaní záznamu v tabuľke vyhľadávania určuje účinnosť tejto techniky. Ak je požadovaný záznam prítomný v prvej pozícii vyhľadávacej tabuľky, vykoná sa len jedno porovnanie. Ak je požadovaný záznam posledný, potom sa musia urobiť n porovnania. Ak má byť záznam niekde vo vyhľadávacej tabuľke, priemerný počet porovnaní bude (n + 1/2). Najhoršou účinnosťou tejto techniky je, že O (n) znamená poradie vykonania.
C Program na vyhľadávanie prvku pomocou techniky lineárneho vyhľadávania.
#include #include void hlavná () {int a [100], n, i, položka, loc = -1; clrscr (); printf ("\ nZadanie čísla elementu:"); scanf ("% d", & n); printf ("Zadajte čísla: \ n"); pre (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nZadajte číslo, ktoré chcete vyhľadať:"); scanf ("% d", & položka); pre (i = 0, i = 0) {printf ("\ n% d sa nachádza v pozícii% d:", položka, miesto + 1); } else {printf ("\ n Položka neexistuje"); } getch (); } Definícia binárneho vyhľadávania
Binárne vyhľadávanie je mimoriadne efektívny algoritmus. Táto vyhľadávacia technika spotrebúva menej času pri hľadaní danej položky pri minimálnych možných porovnávaniach. Ak chcete vykonať binárne vyhľadávanie, najprv musíte zoradiť prvky poľa.
Logika tejto techniky je uvedená nižšie:
- Najprv nájdite stredný prvok poľa.
- Stredný prvok poľa sa porovná s prvkom, ktorý sa má vyhľadávať.
Môžu nastať tri prípady:
- Ak je prvok požadovaným prvkom, vyhľadávanie je úspešné.
- Keď je prvok menší ako požadovaná položka, vyhľadajte iba prvú polovicu poľa.
- Ak je väčšia ako požadovaný prvok, vyhľadajte v druhej polovici poľa.
Opakujte rovnaké kroky, až kým sa v oblasti vyhľadávania nájde alebo nevyčerpá prvok. V tomto algoritme sa znižuje vyhľadávacia oblasť. Preto počet porovnaní je najviac log (N + 1). Ako výsledok je to efektívny algoritmus v porovnaní s lineárnym vyhľadávaním, ale pole musí byť rozdelené pred vykonaním binárneho vyhľadávania.
C Program nájsť prvok s binárnou technikou vyhľadávania.
#include void hlavná () {int i, beg, end, middle, n, search, array [100]; printf ("Zadajte číslo elementu \ n"); scanf ( "% d", a n); printf ("Zadajte% d čísla \ n", n); pre (i = 0, i <n; i ++) scanf ("% d", & array [i]); printf ("Zadajte číslo, ktoré sa má vyhľadať \ n"); scanf ("% d", & vyhľadávanie); beg = 0; koniec = n - 1; stredný (beg + koniec) / 2; zatiaľ čo (beg <= end) {if (pole [stredný] koniec) printf ("Vyhľadávanie je neúspešné!% d nie je v zozname. \ n", vyhľadávanie); getch (); } Kľúčové rozdiely medzi lineárnym vyhľadávaním a binárnym vyhľadávaním
- Lineárne vyhľadávanie je iteračné a používa sekvenčný prístup. Na druhej strane binárne vyhľadávacie nástroje rozdeľujú a podmanňujú prístup.
- Časová zložitosť lineárneho vyhľadávania je O (N), zatiaľ čo binárne vyhľadávanie má O (log 2 N).
- Najlepší čas v prípade lineárneho vyhľadávania je pre prvý prvok, tj O (1). Na rozdiel od toho v binárnom vyhľadávaní ide o stredný prvok, tj O (1).
- V lineárnom vyhľadávaní je najhorší prípad pri hľadaní prvku počet N porovnaní. Na rozdiel od toho je to log 2 N počet porovnaní pre binárne vyhľadávanie.
- Lineárne vyhľadávanie môže byť implementované v poli, ako aj v prepojenom zozname, zatiaľ čo binárne vyhľadávanie nemožno implementovať priamo na prepojenom zozname.
- Ako vieme, binárne vyhľadávanie vyžaduje zoraďované pole, ktoré je dôvodom. Vyžaduje spracovanie na vloženie na správne miesto na udržanie triedeného zoznamu. Naopak lineárne vyhľadávanie nevyžaduje triedenie prvkov, preto sa na koniec zoznamu jednoducho vložia prvky.
- Lineárne vyhľadávanie sa ľahko používa a nie sú potrebné žiadne objednané prvky. Na druhej strane algoritmus binárneho vyhľadávania je však zložitý a prvky sú nevyhnutne usporiadané v poradí.
záver
Obidva lineárne a binárne vyhľadávacie algoritmy môžu byť užitočné v závislosti od aplikácie. Keď je pole dátová štruktúra a prvky sú usporiadané v usporiadanom poradí, pre rýchle vyhľadávanie je preferované binárne vyhľadávanie. Ak je prepojený zoznam dátová štruktúra bez ohľadu na to, ako sú usporiadané prvky, je lineárne vyhľadávanie prijaté z dôvodu nedostupnosti priamej implementácie binárneho algoritmu vyhľadávania.
Typický binárny algoritmus vyhľadávania nemôže byť použitý pre prepojený zoznam, pretože prepojený zoznam má dynamický charakter a nie je známe, kde je skutočne priradený stredný prvok. Preto existuje požiadavka navrhnúť variáciu binárneho vyhľadávacieho algoritmu, ktorý môže pracovať aj na prepojenom zozname, pretože binárne vyhľadávanie je rýchlejšie ako pri lineárnom vyhľadávaní.
