Algoritmi de căutare liniare și binare explicate

Capacitatea de a căuta unele date este un aspect important al informaticii. Algoritmii de căutare sunt utilizați pentru a căuta un anumit element dintr-un set de date.

Algoritmii returnează un rezultat boolean (adevărat sau fals) la o interogare de căutare. De asemenea, pot fi modificate pentru a da poziția relativă a valorii găsite.

Pentru acest articol, algoritmii se vor concentra asupra determinării dacă există o valoare.

Algoritmi de căutare liniară

Căutarea liniară este, de asemenea, cunoscută sub numele de căutare secvențială. În acest tip de căutare, fiecare valoare dintr-o listă este vizitată una câte una în mod ordonat în timp ce se verifică dacă există valoarea dorită.

Algoritmul verifică valoarea după valoare până când găsește valoarea pe care o căutați sau rămâne fără valori de căutat. Când rămâne fără valori pentru căutare, înseamnă că interogarea dvs. de căutare nu există în listă.

Un algoritm de căutare secvențială ia ca listă valorile și elementul dorit din listă ca parametri. Rezultatul de returnare este inițializat ca

Fals și se va schimba în Adevărat când se găsește valoarea dorită.

Vedeți mai jos implementarea Python ca exemplu:

def linearSearch (lista mea, articol):

găsit = Fals

index = 0

în timp ce indexul

dacă lista mea [index] == element:

găsit = Adevărat

altceva:

index = index + 1

retur găsit

Analiza algoritmului

Cel mai bun scenariu apare atunci când elementul dorit este primul din listă. Cel mai rău caz apare atunci când elementul dorit este ultimul din listă (al n-lea element). Prin urmare, complexitatea timpului pentru căutarea liniară este O (n).

Scenariul mediu de caz din algoritmul de mai sus este n / 2.

Legate de: Ce este notația Big-O?

Căutare liniară modificată

Este important să știm că algoritmul utilizat presupune că i se furnizează o listă aleatorie de articole. Adică, articolele din listă nu au o ordine specială.

Să presupunem că articolele erau într-o anumită ordine, să zicem de la cel mai mic la cel mai mare. Ar fi posibil să se obțină un anumit avantaj în calcul.

Luați un exemplu de a căuta 19 în lista dată: [2, 5, 6, 11, 15, 18, 23, 27, 34]. După ce ați ajuns la 23, ar deveni clar că elementul căutat nu există în listă. Prin urmare, nu ar mai fi important să continuați căutarea în restul articolelor din listă.

Algoritmi de căutare binară

Ați văzut cum o listă ordonată poate reduce calculul necesar. Algoritmul de căutare binară profită și mai mult de această eficiență pe care o introduce o listă ordonată.

Algoritmul începe prin luarea unei valori medii a unei liste ordonate și verificarea dacă este valoarea dorită. Dacă nu este, atunci se verifică valoarea dacă este mai mică sau mai mare decât valoarea dorită.

Dacă este mai puțin, atunci nu este nevoie să verificați jumătatea inferioară a listei. În caz contrar, dacă este mai mare, atunci trece la jumătatea superioară a listei.

Legate de: Ce este recursivitatea și cum o utilizați?

Indiferent de orice sublistă (stânga sau dreapta) este aleasă, valoarea din mijloc va fi din nou determinată. Valoarea este verificată din nou dacă este valoarea necesară. În caz contrar, se verifică dacă este mai mică sau mai mare decât valoarea solicitată.

Acest proces se repetă până când se găsește o valoare dacă există.

Implementarea Python de mai jos este pentru algoritmul de căutare binară.

binarySearch def (lista mea, articol):

scăzut = 0

high = len (lista mea) - 1

găsit = Fals

în timp ce scăzut <= ridicat și nu a fost găsit:

mid = (low + high) // 2

dacă lista mea [mijloc] == element:

găsit = Adevărat

element elif

ridicat = mijlociu - 1

altceva:

scăzut = mijloc + 1

retur găsit

Analiza algoritmului

Cel mai bun caz apare atunci când elementul dorit este elementul de mijloc. Cel mai rău scenariu nu este totuși la fel de simplu. Urmați analiza de mai jos:

După prima comparație, n / 2 articole vor fi lăsate. După al doilea, n / 4 articole vor fi lăsate. După a treia, n / 8.

Observați că numărul de articole continuă să se înjumătățească până când ajung la n / 2i unde i este numărul de comparații. După toate despărțirile, ajungem cu doar 1 articol.

Asta implică:

n / 2i = 1

Prin urmare, căutarea binară este O (log n).

Trecând la Sortare

În căutarea binară, am considerat un caz în care matricea dată era deja comandată. Dar să presupunem că aveți un set de date neordonat și că doriți să efectuați căutări binare pe acesta. Ce ai face?

Răspunsul este simplu: sortează-l. Există o serie de tehnici de sortare în informatică care au fost bine cercetate. Una dintre aceste tehnici pe care o puteți începe să studiați este algoritmul de sortare a selecției, în timp ce avem o mulțime de ghiduri legate și de alte domenii.

Cum se folosește Sortarea selecției

Sortarea selecției este puțin dificil de înțeles pentru începători, dar nu este prea dificilă odată ce obțineți schimbarea lucrurilor.

Citiți în continuare

Despre autor