Diferența majoră între căutarea liniară și căutarea binară este că căutarea binară durează mai puțin timp pentru a căuta un element din lista de elemente sortată. 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 sortate în timp ce în căutarea liniară nu există o astfel de condiție prealabilă. Deși ambele metode de căutare utilizează tehnici diferite care sunt discutate mai jos.
Diagramă de comparație
| Bazele de comparație | Căutarea liniară | Căutare binară |
|---|---|---|
| Complexitatea timpului | PE) | O (log 2N) |
| Cel mai bun caz | Primul element O (1) | Elementul central O (1) |
| Condiție prealabilă pentru o matrice | Nu este necesar | Arramentul trebuie să fie în ordine ordonată |
| Cel mai rău caz pentru numărul de elemente N | Sunt necesare comparații N | Se poate concluziona după numai 2 N comparații log |
| Poate fi implementat pe | Array și lista conectată | Nu pot fi implementate direct pe lista conectată |
| Introduceți operația | Introduceți ușor la sfârșitul listei | Solicitați procesarea pentru a insera la locul potrivit pentru a păstra o listă sortată. |
| Tipul algoritmului | Iterativ în natură | Împărțirea și cucerirea în natură |
| Utilitate | Ușor de folosit și nu necesită elemente comandate. | Oricum, algoritmul și elementele dificile ar trebui organizate în ordine. |
| Linii de cod | Mai puțin | Mai Mult |
Definiția Căutării liniare
Într-o căutare liniară, fiecare element al unei matrice este preluat unul câte unul într-o ordine logică și verificat dacă este sau nu elementul dorit. O căutare va fi nereușită dacă toate elementele sunt accesate și elementul dorit nu este găsit. În cel mai rău caz, numărul unui caz mediu ar trebui să scanăm jumătate din dimensiunea matricei (n / 2).
Ca urmare, căutarea liniară poate fi definită ca tehnica care traversează array secvențial pentru a localiza elementul dat. Programul prezentat mai jos ilustrează căutarea unui element al matricei utilizând căutarea.
Eficiența căutării liniare
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 doar o singură comparație. Atunci când înregistrarea dorită este ultima, atunci trebuie efectuate n comparații. Dacă înregistrarea trebuie să apară undeva în tabelul de căutare, în medie, numărul de comparații va fi (n + 1/2). Eficiența celui mai rău caz al acestei tehnici este O (n), care reprezintă ordinea execuției.
Program C pentru a căuta un element cu tehnică de căutare liniară.
#include #include void principal () {int a [100], n, i, element, loc = -1; clrscr (); printf ("\ nIntroduceți numărul elementului:"); scanf ("% d", & n); printf ("Introduceți numerele: \ n"); pentru (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nIntroduceți numărul care urmează să fie căutat:"); scanf ("% d", & element); pentru (i = 0; i = 0) {printf ("\ n% d se găsește în poziția% d:", element, loc + 1); } altceva {printf ("\ 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 elementului dat în comparații posibile minime. Pentru a face căutarea binară, mai întâi trebuie să sortați elementele de matrice.
Logica din spatele acestei tehnici este dată mai jos:
- Mai întâi, găsiți elementul intermediar al matricei.
- Elementul de mijloc al matricei este comparat cu elementul care trebuie căutat.
Există trei cazuri care ar putea apărea:
- Dacă elementul este elementul necesar, atunci căutarea este reușită.
- Când elementul este mai mic decât elementul dorit, căutați doar prima jumătate a matricei.
- Dacă este mai mare decât elementul dorit, căutați în a doua jumătate a matricei.
Repetați aceiași pași până când un element este găsit sau epuizat în zona de căutare. În acest algoritm, de fiecare dată când zona de căutare este redusă. Prin urmare, numărul de comparații este cel mult log (N + 1). Ca rezultat, este un algoritm eficient în comparație cu căutarea liniară, dar matricea trebuie să fie sortată înainte de a efectua căutarea binară.
Programul C pentru a găsi un element cu tehnica de căutare binară.
#include void principal () {int i, cer, sfârșit, mijloc, n, căutare, matrice [100]; printf ("Introduceți numărul elementului \ n"); scanf ( "% d", & n); printf ("Introduceți numerele% d \ n", n); pentru (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Introduceți numărul care urmează să fie căutat \ n"); scanf ("% d", & căutare); beg = 0; end = n - 1; mijloc = (cerșit + sfârșit) / 2; în timp ce (beg <= end) {if (array [middle] end) printf ("Căutarea este nereușită!% d nu este prezentă în listă. \ n", căutare); getch (); } Diferențe cheie între căutare liniară și căutare binară
- Căutarea liniară are un caracter iterativ și folosește abordarea secvențială. Pe de altă parte, aplicațiile binare de căutare împart și împart abordarea.
- Complexitatea timpului de căutare liniară este O (N) în timp ce căutarea binară are O (log 2 N).
- Cel mai bun caz în căutarea liniară este pentru primul element, adică, O (1). În schimb, în căutarea binară, este pentru elementul intermediar, adică O (1).
- În căutarea liniară, cel mai rău caz pentru căutarea unui element este N numărul de comparație. În schimb, este log 2 N numărul de comparație pentru căutarea binară.
- Căutarea liniară poate fi implementată într-o matrice, precum și în lista asociată, în timp ce căutarea binară nu poate fi implementată direct pe lista conectată.
- După cum știm căutarea binară necesită matricea sortată care este motivul Este necesară procesarea pentru a insera la locul ei adecvat pentru a menține o listă sortată. Dimpotrivă, căutarea liniară nu necesită elemente sortate, astfel încât elementele să fie ușor inserate la sfârșitul listei.
- Căutarea liniară este ușor de folosit și nu este nevoie de elemente comandate. Pe de altă parte, algoritmul de căutare binar este totuși dificil, iar elementele sunt aranjate neapărat în ordine.
Concluzie
Atât algoritmii de căutare liniare cât și binare pot fi utile în funcție de aplicație. Atunci când o matrice este structura de date și elementele sunt aranjate în ordine ordonată, atunci căutarea binară este preferată pentru căutarea rapidă . Dacă lista legată este structura de date indiferent de modul în care sunt aranjate elementele, căutarea liniară este adoptată din cauza indisponibilității implementării directe a algoritmului de căutare binar.
Algoritmul de căutare binar tipic nu poate fi folosit pentru lista de linkuri deoarece lista legată este dinamic în natură și nu se știe unde este atribuit elementul intermediar. 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ă decât executarea unei căutări liniare.
