Căutarea liniară și căutarea binară sunt algoritmi comuni utilizați pentru a găsi elemente într-o listă. Înțelegerea numărului așteptat de comparații fiecare algoritm face poate ajuta la alegerea metodei cele mai eficiente pentru situații specifice. Acest articol compară comparațiile așteptate în metodele liniare de căutare binare față de.

Căutare liniară

Căutarea liniară verifică fiecare element din listă secvenţial până când găseşte ţinta sau ajunge la final. Numărul estimat de comparaţii depinde de prezenţa ţintei şi poziţia acesteia în listă.

Dacă lista conține elemente n și obiectivul este la fel de probabil să fie în orice poziție, numărul preconizat de comparații este:

Comparații preconizate = (n + 1) / 2

Asta pentru că, în medie, căutarea va găsi ţinta la jumătatea listei.

Căutare binară

Căutare binară funcționează pe liste sortate prin împărțirea repetată a intervalului de căutare în jumătate. Eficiența sa depinde de dimensiunea listei și poziția țintei.

În cel mai bun caz, ținta se află la mijloc, necesită doar o comparație. În cel mai rău caz, este nevoie de aproximativ log2] n comparații.

Presupunând că obiectivul este la fel de probabil să fie în orice poziție, numărul preconizat de comparații este aproximativ:

Comparații preconizate log 2 n

Rezumat de comparare

  • Căutarea liniară are un număr de comparare aşteptat (n + 1) / 2.
  • Căutarea binară are un număr de comparaţii aşteptat de aproximativ log2 n.
  • Căutarea binară necesită, în general, mai puţine comparaţii pentru listele mari.
  • Căutarea liniară poate fi preferabilă pentru liste mici sau nesortate.