La ricerca lineare e la ricerca binaria sono algoritmi comuni utilizzati per trovare elementi all'interno di un elenco. Capire il numero atteso di confronti che ogni algoritmo fa può aiutare a scegliere il metodo più efficiente per situazioni specifiche.

Ricerca lineare

La ricerca lineare controlla ogni elemento nella lista sequenziale fino a quando non trova l'obiettivo o raggiunge la fine. Il numero atteso di confronti dipende dal fatto che il bersaglio è presente e dalla sua posizione nell'elenco.

Se l'elenco contiene n[] elementi e l'obiettivo è altrettanto probabile che sia in qualsiasi posizione, il numero atteso di confronti è:

Confronti previsti = (n + 1) / 2

Questo perché, in media, la ricerca troverà l'obiettivo a metà strada attraverso la lista.

Ricerca binaria

La ricerca binaria funziona su elenchi ordinati dividendo ripetutamente l'intervallo di ricerca a metà. La sua efficienza dipende dalla dimensione dell'elenco e dalla posizione del bersaglio.

Nel caso migliore, il bersaglio è al centro, che richiede solo un confronto. Nel peggiore dei casi, ci vogliono approssimativamente ]log]]2 n]] confronti.

Se l'obiettivo è altrettanto probabile che sia in qualsiasi posizione, il numero atteso di confronti è approssimativamente:

Confronti previsti ]2]

Sintesi

  • Ricerca lineare ha un conteggio di confronto previsto (n + 1) / 2.
  • La ricerca binaria ha un numero di confronto previsto di circa log2 n.
  • La ricerca binaria richiede generalmente meno confronti per grandi liste.
  • La ricerca lineare può essere preferibile per le piccole o non assortite liste.