Căutare liniară și căutare binară

Video: 7.1 Linear Search Algorithm with example | linear search in C | Data structures

Conţinut

Cuprins: diferența dintre căutarea liniară și căutarea binară
Diagramă de comparație
Căutare binară
Diferențele cheie
Concluzie
Video explicativ

Diferența dintre căutarea liniară și o căutare binară este că în căutarea liniară fiecare element este verificat și comparat și apoi sortat în timp ce în căutarea binară o listă care urmează să fie sortată este împărțită în două părți și apoi sortată. Căutarea și sortarea sunt două concepte principale în programarea computerului. Mulți algoritmi sunt folosiți pentru căutare și sortare, dar cei mai mulți doi algoritmi de căutare și sortare sunt căutarea liniară și căutarea binară.

Diferența dintre căutarea liniară și o căutare binară este funcționarea și eficiența ambilor algoritmi. Căutarea binară este un algoritm mult mai eficient în comparație cu algoritmul de căutare liniară. Iterația sau timpul necesar pentru a compara fiecare valoare înainte de sortare este mai mică în căutarea binară în comparație cu căutarea liniară.

Căutarea liniară este un algoritm foarte complex dacă doriți să căutați un număr dintr-o listă, să comparați și să repetați uneori numărul de valori din listă. Unul câte unul, fiecare element al listei este preluat și comparat cu elementul adiacent. Toate elementele sunt accesate și verificați și apoi se găsește elementul potrivit. Poate fi cel mai rău caz dacă ultimul număr din listă este numărul care trebuie căutat. Căutarea liniară este metoda prin care este traversat tabloul și este fondat elementul care va fi căutat. Dacă vorbim despre eficiență, eficiența este de câte ori programul trebuie să ruleze pentru a găsi numărul. Dacă găsim numărul pe care îl căutăm în prima poziție, atunci trebuie făcută o singură comparație și lucrurile sunt sortate, dar dacă nu, comparațiile trebuie să se facă iar și iar, iar memoria este irosită. În medie, numărul de comparații va fi (n + 1/2). Iar cea mai slabă eficiență a acestei tehnici este O (n) înseamnă ordinea de execuție.

În comparație cu căutarea liniară, căutarea binară este foarte eficientă. În această metodă, tabloul este împărțit în două părți și în acest fel numărul de comparații este foarte mic în comparație cu căutarea binară. Timpul este, de asemenea, mai mic în căutarea binară în comparație cu căutarea liniară. Căutarea binară funcționează în modul în care elementul de mijloc al tabloului este găsit și apoi elementul de mijloc este comparat cu o parte a tabloului. Pot exista trei posibilități care să fie un număr de mijloc poate fi numărul pe care trebuie să îl găsim sau numărul care este mai mic decât numărul de mijloc sau numărul care este mai mare decât mijlocul numărului de mijloc. Numărul de comparații este cel mult jurnal (N + 1). Căutarea binară în comparație cu căutarea liniară este un algoritm eficient în comparație cu căutarea liniară, dar tabloul trebuie sortat înainte de a efectua căutarea binară.

Cuprins: diferența dintre căutarea liniară și căutarea binară

Diagramă de comparație
Căutare binară
Diferențele cheie
Concluzie
Video explicativ

Diagramă de comparație

Bază	Căutare liniară	Căutare binară
Sens	Căutare liniară fiecare element este verificat și comparat și apoi sortat	Căutarea binară o listă care urmează să fie sortată este împărțită în două părți și apoi sortată.
Complexitatea timpului	Complexitatea în timp a căutării liniare este O (N).	Complexitatea în timp a căutării binare este O (jurnal ₂ N)
Tipul de algoritm	Căutarea liniară este iterativă.	Căutarea binară este împărțită și cucerită.
Linie de cod	Într-o căutare liniară, trebuie să scriem mai multe coduri.	Într-o căutare binară, trebuie să scriem mai puțin cod.

Căutare liniară

Căutarea liniară este un algoritm foarte complex dacă doriți să căutați un număr dintr-o listă, să comparați și să repetați de câteva ori numărul de valori din listă. Unul câte unul, fiecare element al listei este preluat și comparat cu elementul adiacent. Toate elementele sunt accesate și verificate, iar apoi se găsește elementul potrivit. Poate fi cel mai rău caz dacă ultimul număr din listă este numărul care trebuie căutat. Căutarea liniară este metoda prin care este traversat tabloul și este fondat elementul care va fi căutat. Dacă vorbim despre eficiență, eficiența este de câte ori programul trebuie să ruleze pentru a găsi numărul. Dacă găsim numărul pe care îl căutăm în prima poziție, atunci trebuie făcută o singură comparație și lucrurile sunt sortate, dar dacă nu, comparațiile trebuie să se facă iar și iar, iar memoria este irosită. În medie, numărul de comparații va fi (n + 1/2). Iar cea mai proastă eficiență a acestei tehnici este O (n) înseamnă ordinea de execuție.

Căutare binară

Pot exista trei posibilități care să fie un număr de mijloc poate fi numărul pe care trebuie să îl găsim sau numărul care este mai mic decât numărul de mijloc sau numărul care este mai mare decât mijlocul numărului de mijloc. Numărul de comparații este cel mult jurnal (N + 1). Căutarea binară în comparație cu căutarea liniară este un algoritm eficient în comparație cu căutarea liniară, dar tabloul trebuie sortat înainte de a efectua căutarea binară.

Diferențele cheie

Căutare liniară fiecare element este verificat și comparat și apoi sortat în timp ce căutarea binară o listă care urmează să fie sortată este împărțită în două părți și apoi sortată.
Complexitatea în timp a căutării liniare este 0 (N), în timp ce Complexitatea timpului căutării binare este O (jurnal)₂N).
Căutarea liniară este iterativă, în timp ce căutarea binară este împărțită și cuceri.
În căutarea liniară, trebuie să scriem mai multe coduri, în timp ce în căutarea binară trebuie să scriem mai puțin cod.