Complessità di tempo della ricerca binaria per un array non ordinato

Question

Sono bloccato con due complessità di tempo. Per fare una ricerca binaria con array ordinato è O (logN). Quindi per cercare un array non ordinato dobbiamo prima ordinarlo in modo che diventi O (NlogN). Quindi possiamo eseguire la ricerca binaria che fornisce la complessità come O (N), ma ho letto che potrebbe essere O (NlogN). Che è corretto?

Answer 1

La ricerca binaria è per gli elenchi "Ordinati". La complessità è O (logn).

La ricerca binaria non funziona per gli elenchi "non ordinati". Per queste liste basta fare una ricerca diretta partendo dal primo elemento; questo dà una complessità di O (n). Se dovessi ordinare l'array con MergeSort o qualsiasi altro algoritmo di O (nlogn), la complessità sarebbe O (nlogn).

O (log n) < O (n) < O (nlogn)

Answer 2

La risposta alla tua domanda è nella vostra domanda stessa. Stai prima ordinando la lista. Se si ordina l'elenco utilizzando l'ordinamento rapido o di unione, la complessità diventa o (n log n). La parte 1 prende il sopravvento. La seconda parte dell'esecuzione di una ricerca binaria viene eseguita nella 'Lista ordinata'. La complessità della ricerca binaria è o (log n). Pertanto alla fine la complessità del programma rimane o (n log n). Tuttavia, se si desidera calcolare la mediana dell'array, non è necessario ordinare l'elenco. Una semplice applicazione di una ricerca lineare o sequenziale può aiutarti in questo.

Answer 3

La complessità temporale della ricerca lineare è O(n) e quella della ricerca binaria è O(log n) (registro base-2). Se abbiamo una matrice non ordinata e vogliamo usare la ricerca binaria per questo, dobbiamo prima ordinare l'array. E qui dobbiamo passare un tempo O(n logn) per ordinare l'array e quindi passare il tempo a cercare l'elemento.