La ricerca binaria sembra superiore, perché il comitato di C ++ ha ancora trovato nella libreria dell'algoritmo?

Non tutte le liste sono ordinate, ma a volte ci sono cose che vorremmo trovare.

Anche quicksort è O(n log n) , il che significa che richiede più tempo di O(n) .

Tieni presente che da un punto di vista teorico è impossibile lasciare che l'ordinamento e la ricerca siano più rapidi del trovare. Per ordinare, è necessario esaminare ogni elemento almeno una volta per determinare la sua posizione. Per trovare, nel peggiore dei casi, è necessario esaminare ogni elemento una volta (purché non siano ordinati). Solo quando stai facendo ricerche ripetute, potrebbe essere sensato prima ordinare gli elementi (una "tassa di avvio") per avere ricerche "meno costose".

Come altri hanno già detto, la ricerca binaria fornisce una soluzione ad alte prestazioni quando i dati vengono ordinati, mentre la ricerca è più lenta ma non ha quel vincolo preselezionato.

Inoltre è importante notare che per ordinare un vettore è necessario copiarlo e mutarlo o semplicemente mutarlo. Questo non è solo costoso, ma ha effetti collaterali che potrebbero non corrispondere alla semantica del tuo algoritmo.

Inoltre C ++ 11 definisce le nuove collezioni std :: unordered_set e std :: unordered_map che per definizione non sono compatibili con gli algoritmi di ricerca binaria.

Trova è pensato per operare su qualsiasi contenitore STL generico, alcuni dei quali sono costosi da ordinare. Esistono modi più rapidi per trovare un elemento con la giusta struttura dati, ad esempio con std::set , e quella classe ha una funzione membro find .

Inoltre, la premessa della tua domanda è falsa. La complessità asintotica di quicksort è O (n ^ 2), non O (log 2n) o O (n log n). Molte persone sembrano confonderlo con la complessità media di quicksort .

Quicksort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare.

Oltre a ciò che è stato menzionato, anche dato un array che era già stato ordinato, se ha, ad esempio, solo un misero 10 elementi in esso, la ricerca del tempo lineare rischia di sovraperformare strongmente la ricerca binaria logaritmica. La complessità algoritmica non equivale alla velocità. Descrive la scalabilità, ma la scalabilità non è così utile per gli input che non vengono scalati.

Oltre a ciò una ricerca binaria è meno generalizzata e meno applicabile, dal momento che richiede iteratori ad accesso casuale che le strutture collegate generalmente non possono fornire. Una ricerca sequenziale richiede solo iteratori in avanti che praticamente qualsiasi struttura dati può fornire.