Ricerca binaria ripasso

Ricerca binaria: definizione

È un algoritmo per la ricerca di un elemento in un array ordinato. Divide la lista in metà ad ogni passo.

Condizioni per la ricerca binaria

L'array deve essere ordinato. Altrimenti, il risultato è imprevedibile.

Funzionamento della ricerca binaria

1. Inizia con i limiti inferiore e superiore. 2. Calcola il punto medio. 3. Confronta il valore cercato con l'elemento centrale. 4. Ripeti la ricerca nella metà pertinente.

Ricerca binaria è più veloce di:

Ricerca lineare, specialmente per array grandi.

Vero o falso: la ricerca binaria funziona su array non ordinati.

Falso. Deve essere applicata solo su array ordinati.

Esempio di array ordinato

[1, 3, 5, 7, 9] - Ricerca di 5: trova in posizione 2.

Formula per trovare l'indice centrale

Indice centrale: $\displaystyle mid = \frac{lower + upper}{2}$

Numero massimo di operazioni

È $\displaystyle O( ext{log} n)$, dove n è il numero di elementi.

Passaggi della ricerca binaria

1. Calcola il punto medio. 2. Confronta. 3. Aggiorna limiti. 4. Ripeti finché non trovi l’elemento o gli intervalli si sovrappongono.

Limiti della ricerca binaria

Funziona solo su array ordinati e non è ottimale per piccole dimensioni.

Vero o falso: la ricerca binaria modifica l'array.

Falso. Non modifica l'array, cerca solo.

Ricerca binaria vs ricerca lineare

Ricerca binaria è più efficiente su grandi dataset, ricerca lineare è più semplice.

Cosa rappresenta 'lower' e 'upper'?

'lower' è l'indice iniziale, 'upper' è l'indice finale dell'array durante la ricerca.

Efficienza della ricerca binaria

Richiede log2(n) confronti nel caso migliore, medio e peggiore.

Esempio di ricerca binaria in pseudocodice

funzione ricercaBinaria(array, valore): inizio = 0 fine = lunghezza(array) - 1 mentre inizio ≤ fine: ... [implementazione]

Cosa è l'array?

Una struttura dati che contiene una sequenza di elementi dello stesso tipo.

Complessità temporale della ricerca binaria?

La complessità temporale è $\displaystyle O( ext{log} n)$, dove $\displaystyle n$ è il numero di elementi.

Complessità spaziale della ricerca binaria?

La complessità spaziale è $\displaystyle O(1)$ per la versione iterativa e $\displaystyle O( ext{log} n)$ per la versione ricorsiva.

La ricerca binaria funziona su dati non ordinati: vero o falso?

Falso. La ricerca binaria richiede che i dati siano ordinati.

Differenza tra ricerca binaria e lineare?

La ricerca binaria è $\displaystyle O( ext{log} n)$, mentre la ricerca lineare è $\displaystyle O(n)$.

Quando si verifica il caso peggiore nella ricerca binaria?

Si verifica quando l'elemento cercato non è presente o è all'estremo.

Formula per calcolare il numero di confronti nella ricerca binaria?

Il numero massimo di confronti è $\displaystyle ext{log}_2(n) + 1$.

Cosa succede se l'array non è ordinato?

La ricerca binaria non funzionerà correttamente e darà risultati errati.

Esempio di complessità temporale con 16 elementi?

Con 16 elementi, la ricerca binaria effettua al massimo 5 confronti: $\displaystyle 2^5 = 32$.

Condizioni per l'applicazione della ricerca binaria?

- Dati ordinati - Accesso casuale agli elementi

La ricerca binaria è più veloce della ricerca lineare: vero o falso?

Vero, per grandi dataset, grazie alla sua complessità logaritmica.

Cosa influisce sulla performance della ricerca binaria?

La dimensione dell'array e l'ordinamento dei dati influiscono direttamente.

Partizione dell'array nella ricerca binaria?

L'array viene diviso in due metà ad ogni confronto, riducendo la ricerca.

Applicazione: ricerca in un elenco ordinato

La ricerca binaria è utilizzata per trovare rapidamente un elemento in un elenco ordinato.

Vantaggio della ricerca binaria

Richiede solo $\displaystyle O( ext{log } n)$ confronti per trovare un elemento, molto più efficiente di $\displaystyle O(n)$.

Vero o falso: la ricerca binaria funziona su dati non ordinati.

Falso. Necessita che i dati siano ordinati per funzionare correttamente.

Situazione pratica: ricerca in lettere alfabetiche.

Quando si cerca una lettera in un dizionario ordinato, la ricerca binaria è molto efficace.

Comparazione: ricerca binaria vs. ricerca lineare.

Ricerca binaria è più veloce in $\displaystyle O( ext{log } n)$, mentre la ricerca lineare è $\displaystyle O(n)$.

Esempio di uso: trovare un numero in un elenco.

Cerca 25 in [1, 5, 10, 15, 20, 25, 30]. Risultato: trovato in posizione 5.

Applicazione in database

Utilizzata per migliorare le prestazioni delle query su tabelle ordinate.

Vantaggio nell'analisi dei dati

Consente di analizzare grandi dataset in modo rapido e con meno risorse.

Completa: La ricerca binaria è ideale per __________.

elenco ordinato di elementi.

Vero o falso: la ricerca binaria richiede dati già ordinati.

Vero. È essenziale che i dati siano ordinati prima dell'uso.

Applicazione nei linguaggi di programmazione

Utilizzata in algoritmi di ricerca e ordinamento in linguaggi come Python e Java.

Cause ed effetti: come migliora la ricerca?

Riduce il numero di confronti, aumentando l'efficienza, specialmente in set di dati grandi.