Perché la ricerca binaria, che ha bisogno di dati ordinati, è considerata migliore della ricerca lineare?

Are there any practical considerations that I am overlooking which making binary search better than linear search?

Sì - devi fare l'ordinamento O (n log n) solo una volta, e poi puoi fare la ricerca binaria O (log n) tutte le volte che vuoi, mentre la ricerca lineare è O (n) ogni volta.

Ovviamente, questo è solo un vantaggio se in effetti fai più ricerche sugli stessi dati. Ma gli scenari "scrivi una volta, leggi spesso" sono abbastanza comuni.

L'assunto di base è che tu non effettui una ricerca.

Quindi, se hai bisogno di cercare gli stessi dati più volte, devi solo ordinare una volta e trarre profitto dalla ricerca binaria.

Se esegui una ricerca frequente e hai cambiato i dati, vale la pena utilizzare un elenco ordinato in cui le nuove voci vengono ordinate nell'elenco.

Quindi in pratica la ricerca binaria è migliore quando si cerca la stessa lista più volte senza la necessità di ricorrere.

Quando devi ordinare ogni volta prima della ricerca, non c'è alcun vantaggio.

Si noti che esistono algoritmi di ordinamento molto veloci quando l'elenco è già ordinato (o quasi ordinato). La maggior parte delle determinazioni delle prestazioni si aspetta un elenco non ordinato.

perché una volta che hai una lista ordinata non hai bisogno di riordinarla ogni volta, il che significa che se hai più di O (log n) le ricerche in via di ordinamento ti procureranno un guadagno vincente ( O(n log n + k log n) vs O(k*n)

Immagina due elenchi telefonici.

Una rubrica telefonica ha i nomi in ordine alfabetico. Per trovare la voce desiderata, apri la parte centrale, controlla la voce, quindi scorri in avanti o indietro a seconda che superi o non superi la soglia.

L'altra rubrica ha i nomi in ordine casuale. Per trovare la voce desiderata, inizi dall'inizio e continua fino a trovare quello che vuoi.

Il secondo libro funzionerà in qualsiasi città di dimensioni ragionevoli?

Penso che il valore della ricerca binaria sulla ricerca lineare sia contestuale. Se si inizia con un enorme set di dati non ordinati e si prevede di estrarre solo un piccolo numero di elementi da esso, l'ordinamento e l'esecuzione di una ricerca binaria saranno lenti. Se, tuttavia, mantieni un elenco ordinato per tutta la durata della tua applicazione e accedi regolarmente, la ricerca binaria è un modo molto migliore per andare.

Come molti altri hanno risposto, la ricerca binaria è davvero preferibile perché la fase di smistamento può essere eseguita solo una volta e la ricerca effettiva può essere eseguita tutte le volte che vuoi. Tuttavia, per determinati valori di n (ad esempio alcune dimensioni di input), la ricerca binaria è sempre più performante della ricerca lineare (anche per una singola esecuzione).

Il "punto di svolta" viene calcolato risolvendo l'equazione della complessità asintotica:

n log n + log n = n

Come puoi vedere su Wolfram Alfa esiste un valore numerico per n che garantisce che la ricerca binaria e l'ordinamento siano sempre più veloci della sola ricerca lineare. Ovviamente il valore attuale di n che funziona nel tuo caso dipende da molti fattori che possono essere difficili da stimare.

Secondo questo interessante articolo di Mark Probst, che include alcuni misure approfondite sulle prestazioni dei processori attuali:

If you need to search through a sorted array of integers and performance is really, really important, use linear search if your array is below around 64 elements in size, binary search if it’s above.

In parole semplici:

Se hai una lista non ordinata con dieci miliardi di elementi e l'elemento che stai cercando è l'ultimo, finirai per leggere i dieci miliardi di elementi.

Nel caso della ricerca binaria, l'indicizzazione può essere fatta solo una volta. Gli inserimenti successivi possono essere fatti nel posto giusto per mantenere l'ordine.

Sebbene siano già stati elencati molti buoni motivi per cui "la ricerca binaria è migliore", potremmo anche dare un'occhiata ai vantaggi dal punto di vista dell'utente:

Anche se normalmente puoi vivere molto bene con il breve intervallo di attesa tra i dati che digitano le azioni quando fai un inserto ordinato, vuoi che la "ricerca" sia il più veloce possibile. Dal punto di vista dell'utente, l'inserimento ordinato combinato con una ricerca binaria offre la migliore esperienza utente possibile.