la ricerca binaria

Question

Quindi, voglio capire di più su ricerca binaria, perché io non capisco. La ricerca binaria richiede un presupposto che una matrice è ordinato. Ho capito bene? Sembra un metodo dovrebbe controllare questo presupposto e un'eccezione se non è soddisfatta. Ma, perché sta controllando la precondizione una cattiva idea?

Answer 1

E 'una cattiva idea, perché la verifica i dati vengono ordinati prende le misure n. Tutta la ricerca è di circa passi log(n).
Se avete intenzione di controllare, si potrebbe anche fare una ricerca lineare.

Answer 2

Il punto centrale di una ricerca binaria è che, dal momento che i dati è già ordinato, è possibile individuare rapidamente le informazioni desiderate.

Prendere la rubrica telefonica, che è allineati secondo cognome.

Come si fa a trovare qualcuno in rubrica? Si apre fino a una pagina, che si assumono sarà vicino a quello che si desidera, e quindi avviare sfogliando le pagine.

Ma non capovolgere una pagina ogni volta, se vi siete persi da un sacco, si ribalta un gruppo di pagine, e poi finalmente iniziare lanciando uno alla volta, fino a quando finalmente si inizia a guardare una singola pagina.

Questo è ciò che fa ricerca binaria. Dal momento che i dati sono ordinati, si sa che può saltare un sacco e fare un altro aspetto, e sarà concentrarsi sulle informazioni che si desidera.

Una ricerca binaria fa 1 di confronto per ogni numero raddoppiato di elementi. Quindi un elemento di raccolta 1024 richiederebbe circa 10 confronti, al massimo, per trovare le informazioni, o almeno cifra che non è lì.

Se, prima di eseguire l'attuale ricerca binaria, fa un pieno prova generale per verificare se i dati sono ordinati, si potrebbe anche solo fare una scansione per le informazioni. Una full run-through + la ricerca binaria richiederanno N + log2 N operazioni, così per 1024 elementi, sarebbe necessario in tutto 1.034 i confronti, mentre una semplice scansione per le informazioni saranno in media richiede la metà, che è 512.

Quindi, se non è possibile garantire che i dati sono ordinati, non si dovrebbe usare la ricerca binaria, in quanto sarà superato da una scansione semplice.

---

Modifica : Dirò questo, però, si potrebbe aggiungere un debug-unico passo codice per verificare questo, per la cattura di bug nel codice che dovrebbe preparare i dati per la ricerca binaria, ma so che, a causa di quello che ho scritto sopra, questo renderà il tempo totale di esecuzione molto più alto, quindi a seconda di ciò che si vuole fare con questo controllo, si potrebbe o non potrebbe desiderare di aggiungerlo. Ma non dovrebbe essere presente nel codice di rilascio.

Answer 3

Sì, una ricerca binaria coinvolge 0 (log n) passi e verificando l'intera sequenza viene ordinato coinvolge 0 (n) passi. Dal mio punto di vista è bene verificare in modalità di debug, non durante il rilascio.

Answer 4

ricerca binaria presuppone che i dati di input vengono ordinati. Così qui lei ha ragione.

Ora, in generale, la verifica se i dati sono ordinati po 'di tempo. Quindi, l'esecuzione di questo prima di ogni ricerca sarebbe rendere la ricerca molto inefficiente.

Più informazioni.

Si supponga che 'n' è quantità di dati.

ricerca binaria ha bisogno di un'operazione O(log(n)) nel caso peggiore per trovare un elemento. Fare in modo che i dati sono ordinati richiede operazioni O(n).

Quindi, se controlleremo precondizione per ogni volta molto grande n inizieremo trascorrere la maggior parte del tempo sul controllo presupposto che fare ricerca vera e propria.

E non è così difficile dire quando si vedrà un effetto del genere. Ho appena calcolato quanto tempo vi permetterà di trascorrere il pre-cheking vs. ricerca attuale

• Per 1 elemento si spende senza tempo alla ricerca.
• Per 2 elementi si spende il 50% sulla ricerca.
• Per 5 elementi si spende il 46% sulla ricerca
• Per 20 elementi si spende il 22% sulla ricerca.
• Per 100 elementi si spendono 7% sulla ricerca.

E così via. In ogni caso resto in tempo è speso per controllo pre-condizione.

Answer 5

In aggiunta a ciò che chiunque altro ha detto di rimanere a corto di tempo (O (n) per controllare tutti gli elementi, contro O (log (n)) per eseguire la ricerca binaria.)

Penso che si sta equivoco l'idea di una pre-condizione. Pre-condizioni e post-condizioni sono un contratto. Se il presupposto è vero, e si esegue l'algoritmo, allora la vostra condizione post sarà vero. Se il presupposto è falso, allora si effettua alcuna garanzia sulla condizione post.

Quindi, in pratica, la ricerca binaria dice: Se i dati che mi dai è già ordinato, allora posso dirvi la posizione di una parte specifica di dati, o se non è presente, eseguendo circa il log (n) i controlli . Se i dati non sono ordinati, faccio nessuna garanzia circa la mia risposta.

Il lavoro che ti porta dal vostro pre-condizione per il tuo post-condizione, se il vostro algoritmo. In questo caso, la ricerca binaria.

Answer 6

La domanda iniziale presuppone che si sta utilizzando una ricerca binaria su una raccolta di dati. Questo non è sempre il caso. Molte volte si stanno solo cercando di calcolare un numero in un certo intervallo.

Supponiamo che si sta cercando di calcolare l'impostazione ottimale della velocità per un ventilatore. Per qualche motivo non è possibile trovare un'espressione in forma chiusa, in modo da simulare il flusso d'aria a differenti impostazioni di velocità.

Supponendo che la ventola può funzionare a qualsiasi velocità da 0rpm a 5000rpm, in realtà non è necessario generare una lista di possibili velocità. Basta trovare la media del precedente minimo e massimo in ogni fase della ricerca binaria.