Perle di programmazione Problema: controllo della matrice ordinata nella ricerca binaria

Question

In Programming Pearls (seconda edizione) Colonna 5, problema 5 la domanda riguarda l'implementazione della ricerca binaria su una matrice non ordinata.

Come si può aggiungere il controllo parziale la funzione in significativamente meno di O (n-1) costa?

So che è possibile controllare ogni iterazione e ottenere O (log n), ma il suggerimento nella parte posteriore suggerisce che esiste una soluzione O (1).

Qual è quella soluzione?

Answer 1

Sommario

Parzialmente controllando se l'array è ordinato in modo che la ricerca binaria è applicabile può essere fatto in O (log n), come ha detto il PO, e in O (1). Il metodo O (log n) consiste nel controllare ciascuna delle sonde rispetto alla sonda precedente per accertarsi che sia comparabile correttamente (minore di, maggiore di). Il metodo O (1) consiste nel controllare l'elemento finale trovato dalla ricerca binaria e uno accanto ad esso in modo tale che se l'elemento ricercato non è stato trovato, è stata trovata almeno la posizione corretta per l'inserimento. Se l'elemento ricercato è stato trovato, allora questo è un buon controllo parziale O (1).

più lunga spiegazione

La parte del problema prima che il blocco di codice dice che un problema comune è tramite ricerca binaria su un array non ordinato. In sostanza, come utilizzare il controllo parziale per verificare se un array è ordinato in meno di O (n-1)?

La soluzione O (log n) consiste nel controllare ciascuna delle mesh delle sonde di ricerca binaria rispetto alla sonda precedente (è inferiore o superiore a quanto previsto). Questo non garantisce che l'array sia ordinato, ma è un buon controllo parziale.

L'unico controllo O (1) a cui riesco a pensare è quello di verificare il luogo finale che viene ricercato in modo tale che il suo valore e i valori adiacenti coincidano con l'idea di dove dovrebbe essere l'elemento cercato, anche se l'elemento non è stato trovato È un controllo parziale piuttosto buono: se l'elemento viene trovato, probabilmente le cose funzionano correttamente. Se non lo fosse, controlla gli elementi intorno a dove dovrebbe essere tale che ce ne sia uno in meno rispetto all'elemento cercato e poi uno che è maggiore dell'elemento cercato. Tuttavia, mi rendo conto che il controllo in questo modo significa che la ricerca binaria, che è O (log n), è già stata eseguita, quindi non so se questo è veramente O (1). Tuttavia, aggiunge solo O (1) alla ricerca generale, quindi penso che sia applicabile.