Obsah

• Porovnávacia tabuľka
• Definícia lineárneho vyhľadávania
• Definícia binárneho vyhľadávania
• záver

Lineárne vyhľadávanie a binárne vyhľadávanie sú dve metódy, ktoré sa používajú v poliach vyhľadávanie prvky. Vyhľadávanie je proces nájdenia prvku v zozname prvkov uložených v akomkoľvek poradí alebo náhodne.

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 vyžaduje menej času na vyhľadanie prvku zo zoradeného zoznamu prvkov. Z toho vyplýva, že účinnosť metódy binárneho vyhľadávania je vyššia ako lineárne vyhľadávanie.

Ďalším rozdielom medzi nimi je, že existujú predpoklady pre binárne vyhľadávanie, t.j. prvky musia byť triedený zatiaľ čo pri lineárnom vyhľadávaní takéto predpoklady neexistujú. Aj keď obe metódy vyhľadávania používajú rôzne techniky, ktoré sú uvedené nižšie.

1. Porovnávacia tabuľka
2. definícia
3. Kľúčové rozdiely
4. záver

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 na prípad	Prvý prvok O (1)	Stredový prvok O (1)
Predpoklad pre pole	Nevyžaduje sa	Pole musí byť zoradené
Najhorší prípad pre N počet prvkov	Vyžaduje sa N porovnaní	Môže sa uzavrieť iba po prihlásení2N porovnania
Môže byť implementovaný na	Zoznam polí a polí	Nie je možné vykonať priamo v prepojenom zozname
Vložte operáciu	Ľahko vložený na koniec zoznamu	Vyžadujte spracovanie, aby ste ho mohli vložiť na svoje správne miesto, aby ste udržali triedený zoznam.
Typ algoritmu	Iteratívny charakter	Rozdeľte a podmante si prírodu
užitočnosť	Ľahko sa používa a nie sú potrebné žiadne objednané prvky.	V každom prípade by mal byť zložitý algoritmus a prvky usporiadané.
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íska jeden po druhom v logickom poradí a skontroluje sa, či je alebo nie je požadovaným prvkom. Hľadanie bude neúspešné, ak sú prístupné všetky prvky a požadovaný prvok sa nenájde. V najhoršom prípade je možné, že číslo priemerného prípadu bude musieť skenovať polovicu veľkosti poľa (n / 2).

Preto možno lineárne vyhľadávanie definovať ako techniku, ktorá postupne prechádza po poli na lokalizáciu danej položky. Program uvedený nižšie ilustruje vyhľadávanie prvku poľa pomocou vyhľadávania.

efektívnosť lineárneho vyhľadávania

Časová náročnosť alebo počet porovnaní vykonaných pri prehľadávaní záznamu v prehľadávacej tabuľke určuje účinnosť techniky. Ak sa požadovaný záznam nachádza na prvej pozícii tabuľky vyhľadávania, vykoná sa iba jedno porovnanie. Ak je požadovaný záznam posledný, musí sa vykonať porovnanie. Ak má byť záznam niekde vo vyhľadávacej tabuľke, v priemere bude počet porovnaní (n + 1/2). Najhorší prípad účinnosti tejto techniky je O (n) znamená poradie vykonania.

Program C na vyhľadávanie prvku pomocou techniky lineárneho vyhľadávania.

#include #include void main () {int a, n, i, item, loc = -1; clrscr (); f (" nZadajte počet prvkov:"); scanf ("% d", & n); f ("Zadajte čísla: n"); pre (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nZadajte číslo, ktoré sa má prehľadávať:"); scanf ("% d", & item); pre (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; prestávka; }} ak (loc> = 0) {f (" n% d sa nachádza na pozícii% d:", položka, loc + 1); } else {f (" 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 pri hľadaní danej položky menej času pri minimálnom možnom porovnaní. Ak chcete vykonať binárne vyhľadávanie, musíme najprv zoradiť prvky poľa.

Logika tejto techniky je uvedená nižšie:

• Najprv nájdite prostredný prvok poľa.
• Prostredný prvok poľa sa porovná s prvkom, ktorý sa má prehľadávať.

Môžu nastať tri prípady:

1. Ak je požadovaný prvok, je vyhľadávanie úspešné.
2. Ak je prvok menší ako požadovaná položka, vyhľadajte iba prvú polovicu poľa.
3. Ak je väčší ako požadovaný prvok, vyhľadajte v druhej polovici poľa.

Rovnaké kroky opakujte, až kým sa v oblasti vyhľadávania nenájde element alebo sa nevyčerpá. V tomto algoritme sa zakaždým zmenšuje oblasť vyhľadávania. Preto je počet porovnávaní nanajvýš log (N + 1). Výsledkom je efektívny algoritmus v porovnaní s lineárnym vyhľadávaním, ale pole musí byť pred vykonaním binárneho vyhľadávania zoradené.

Program C nájsť prvok s technikou binárneho vyhľadávania.

#include void main () {int i, beg, end, mid, n, search, array; f ("Zadajte číslo prvku n"); scanf ( "% d", a n); f ("Zadajte% d čísla n", n); pre (i = 0; i <n; i ++) scanf ("% d", & array); f ("Zadajte číslo, ktoré sa má vyhľadať n"); scanf ("% d", & search); beg = 0; koniec = n - 1; stredná = (začiatok + koniec) / 2; while (beg <= end) {if (pole <search) beg = middle + 1; else if (array == search) {f ("Vyhľadávanie bolo úspešné. n% d nájdené na mieste% d. n", hľadanie, stredné + 1); prestávka; } else end = mid - 1; stredná = (začiatok + koniec) / 2; } ak (beg> end) f ("Vyhľadávanie neúspešné!% d nie je v zozname prítomné. n", hľadať); getch (); }

1. Lineárne vyhľadávanie má vo svojej podstate iteračný charakter a používa postupný prístup. Na druhej strane, binárne vyhľadávanie implementuje rozdelený a dobyvateľský prístup.
2. Časová zložitosť lineárneho vyhľadávania je O (N), zatiaľ čo binárne vyhľadávanie má O (log₂N).
3. Najlepší čas v lineárnom vyhľadávaní je pre prvý prvok, t. J. O (1). Naopak pri binárnom vyhľadávaní je to pre stredný prvok, t. J. O (1).
4. V lineárnom vyhľadávaní je najhorším prípadom hľadania prvku N počet porovnaní. Na rozdiel od toho je to log₂N počet porovnaní pre binárne vyhľadávanie.
5. Lineárne vyhľadávanie môže byť implementované v poli ako aj v prepojenom zozname, zatiaľ čo binárne vyhľadávanie nemôže byť implementované priamo v prepojenom zozname.
6. Ako vieme, binárne vyhľadávanie vyžaduje usporiadané pole, ktoré je dôvodom. Na udržanie triedeného zoznamu je potrebné vložiť spracovanie na správne miesto. Naopak, lineárne vyhľadávanie nevyžaduje triedené prvky, takže prvky sa dajú ľahko vložiť na koniec zoznamu.
7. 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

V závislosti od aplikácie môžu byť užitočné algoritmy lineárneho aj binárneho vyhľadávania. Ak je matica dátová štruktúra a prvky sú usporiadané v zoradenom poradí, uprednostňuje sa binárne vyhľadávanie rýchlyvyhľadávania. Ak je prepojeným zoznamom dátová štruktúra bez ohľadu na usporiadanie prvkov, prijme sa lineárne vyhľadávanie z dôvodu nedostupnosti priamej implementácie algoritmu binárneho vyhľadávania.

Typický binárny algoritmus vyhľadávania nie je možné použiť na prepojený zoznam, pretože prepojený zoznam má dynamický charakter a nie je známe, kde je stredný prvok skutočne priradený. Preto existuje požiadavka navrhnúť variáciu algoritmu binárneho vyhľadávania, ktorá môže pracovať aj na prepojenom zozname, pretože binárne vyhľadávanie je pri vykonávaní rýchlejšie ako lineárne vyhľadávanie.