Conţinut

• Diagramă de comparație
• Definiția Linear Search
• Definiția Binary Search
• Concluzie

Căutarea liniară și căutarea binară sunt cele două metode utilizate în tablouri in cautarea elementele. Căutarea este un proces de găsire a unui element din lista elementelor stocate în orice ordine sau aleatoriu.

Diferența majoră dintre căutarea liniară și căutarea binară este că căutarea binară necesită mai puțin timp pentru a căuta un element din lista de elemente sortate. Deci se deduce că eficiența metodei de căutare binară este mai mare decât căutarea liniară.

O altă diferență între cele două este că există o condiție prealabilă pentru căutarea binară, adică elementele trebuie să fie sortată în timp ce în căutarea liniară nu există o astfel de condiție prealabilă. Deși ambele metode de căutare folosesc tehnici diferite, care sunt discutate mai jos.

1. Diagramă de comparație
2. Definiție
3. Diferențele cheie
4. Concluzie

Diagramă de comparație

Baza de comparație	Căutare liniară	Căutare binară
Complexitatea timpului	PE)	O (log 2 N)
Cel mai bun timp	Primul element O (1)	Elementul central O (1)
Condiție necesară pentru un tablou	Nu este necesar	Array-ul trebuie să fie în ordine ordonată
Cel mai rău caz pentru N număr de elemente	N sunt necesare comparații	Se poate încheia numai după jurnal2N comparații
Poate fi implementat pe	Lista Array și Link-uri	Nu poate fi implementat direct pe lista legată
Operație de introducere	Se introduce ușor la sfârșitul listei	Solicitați procesarea pentru a insera la locul său corespunzător pentru a menține o listă sortată.
Tip de algoritm	Ierativ în natură	Împărțiți și cuceriți în natură
Utilitate	Ușor de utilizat și nu este nevoie de elemente comandate.	Oricum algoritmul și elementele complicate ar trebui organizate în ordine.
Linii de cod	Mai puțin	Mai Mult

Definiția Linear Search

Într-o căutare liniară, fiecare element al unui tablou este preluat unul câte unul într-o ordine logică și verificat dacă este sau nu elementul dorit. O căutare nu va reuși dacă toate elementele sunt accesate și elementul dorit nu va fi găsit. În cel mai rău caz, numărul unui caz mediu poate fi nevoit să scanăm jumătate din dimensiunea tabloului (n / 2).

Prin urmare, căutarea liniară poate fi definită ca tehnica care parcurge matricea secvențial pentru a localiza elementul dat. Programul oferit mai jos ilustrează căutarea unui element din tablou folosind căutarea.

Eficienţă de căutare liniară

Consumul de timp sau numărul de comparații efectuate în căutarea unei înregistrări într-un tabel de căutare determină eficiența tehnicii. Dacă înregistrarea dorită este prezentă în prima poziție a tabelului de căutare, atunci se face o singură comparație. Când înregistrarea dorită este ultima, atunci trebuie făcute n comparații. Dacă înregistrarea va fi prezentată undeva în tabelul de căutare, în medie, numărul de comparații va fi (n + 1/2). Cea mai slabă eficiență a acestei tehnici este O (n) înseamnă ordinea de execuție.

Programul C să caute un element cu tehnică de căutare liniară.

#include #include void main () {int a, n, i, item, loc = -1; clrscr (); f (" n Introduceți numărul elementului:"); scanf ("% d", & n); f ("Introduceți numerele: n"); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" n Introduceți numărul de căutat:"); scanf ("% d", & element); for (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; pauză; }} if (loc> = 0) {f (" n% d se găsește în poziția% d:", element, loc + 1); } else {f (" n Elementul nu există"); } getch (); }

Definiția Binary Search

Căutarea binară este un algoritm extrem de eficient. Această tehnică de căutare consumă mai puțin timp în căutarea articolului dat în comparații minime posibile. Pentru a face căutarea binară, mai întâi, trebuie să sortăm elementele tabloului.

Logica din spatele acestei tehnici este prezentată mai jos:

• În primul rând, găsiți elementul de mijloc al tabloului.
• Elementul de mijloc al tabloului este comparat cu elementul de căutat.

Există trei cazuri:

1. Dacă elementul este elementul necesar, căutarea are succes.
2. Când elementul este mai mic decât elementul dorit, căutați doar în prima jumătate a tabloului.
3. Dacă este mai mare decât elementul dorit, atunci căutați în a doua jumătate a tabloului.

Repetați aceiași pași până când un element este găsit sau se epuizează în zona de căutare. În acest algoritm, fiecare zonă de căutare se reduce. Prin urmare, numărul de comparații este cel mult log (N + 1). Ca urmare, este un algoritm eficient în comparație cu căutarea liniară, dar matricea trebuie sortată înainte de a efectua căutarea binară.

Programul C pentru a găsi un element cu tehnică de căutare binară.

#include void main () {int i, beg, end, middle, n, search, array; f ("Introduceți numărul elementului n"); scanf ( "% d", & n); f ("Introduceți numerele% d n", n); for (i = 0; i <n; i ++) scanf ("% d", & array); f ("Introduceți numărul care trebuie căutat n"); scanf ("% d", & căutare); cerșire = 0; sfârșit = n - 1; mijloc = (beg + end) / 2; while (beg <= end) {if (array <căutare) beg = middle + 1; else if (array == search) {f ("Căutarea are succes. n% d s-a găsit la locația% d. n", căutare, mijloc + 1); pauză; } else end = mijloc - 1; mijloc = (beg + end) / 2; } if (beg> end) f ("Căutarea nu are succes!% d nu este prezentă în listă. n", căutare); getch (); }

1. Căutarea liniară are caracter iterativ și folosește abordarea secvențială. Pe de altă parte, căutarea binară implementează abordarea divizare și cucerire.
2. Complexitatea în timp a căutării liniare este O (N) în timp ce căutarea binară are O (jurnal)₂N).
3. Momentul cel mai bun în căutarea liniară este primul element adică, O (1). Spre deosebire, în căutarea binară, este pentru elementul de mijloc, adică O (1).
4. În căutarea liniară, cel mai rău caz pentru căutarea unui element este numărul N de comparație. În schimb, este jurnal₂Număr de comparație pentru căutare binară.
5. Căutarea liniară poate fi implementată atât într-un tablou, cât și într-o listă legată, în timp ce căutarea binară nu poate fi implementată direct pe lista legată.
6. După cum știm căutarea binară necesită un tablou sortat, care este motivul. Este necesar ca procesarea să fie introdusă la locul potrivit pentru a menține o listă sortată. Din contră, căutarea liniară nu necesită elemente sortate, astfel încât elementele să fie ușor inserate la sfârșitul listei.
7. Căutarea liniară este ușor de utilizat și nu este nevoie de elemente comandate. Pe de altă parte, algoritmul de căutare binară este totuși complicat, iar elementele sunt neapărat aranjate în ordine.

Concluzie

Atât algoritmii de căutare liniare cât și binarii pot fi utili în funcție de aplicație. Atunci când un tablou este structura de date și elementele sunt aranjate în ordine sortată, este preferată căutarea binară rapidin cautarea. Dacă lista legată este structura de date indiferent de modul în care sunt aranjate elementele, căutarea liniară este adoptată datorită indisponibilității implementării directe a algoritmului de căutare binară.

Algoritmul tipic de căutare binară nu poate fi folosit la o listă legată, deoarece lista legată este de natură dinamică și nu se știe unde este alocat efectiv elementul de mijloc. Prin urmare, există o cerință de a proiecta variația algoritmului de căutare binară care poate funcționa și pe lista legată, deoarece căutarea binară este mai rapidă în execuție decât o căutare liniară.