Ricerca di un elemento a log (n)

Question

mi sono imbattuto alla seguente domanda:

Supponiamo che io modifico un determinato elenco ordinato dei numeri distinti 4n come segue:

Conservare gli elementi in posizione pari (posizioni 2, 4, 6, ... 4n) così come sono. Formare n coppie disgiunte (i, j) sulle posizioni con numeri dispari dove i = 2k + 1 per alcuni k = da 0 a n-1 e j = 2k + 1 per alcuni da k = n a 2n-1.

Ora scambiare gli elementi nelle posizioni i e j per ciascuna di tali coppie. (cioè ogni elemento in una posizione numerata dispari nella prima metà dell'array viene scambiato con qualche elemento in una posizione numerata dispari nella seconda metà dell'array. Nessun elemento è coinvolto in più di uno swap (cioè gli swap sono disgiunti) Non si conoscono queste coppie (i, j) tranne per il fatto che un elemento in una posizione numerata dispari nella prima metà dell'array viene scambiato con un elemento in una posizione numerata dispari nella seconda metà. Ora dato un elemento x, spiegare come si può determinare se o non x è nella (nuova rëshu ffl ndr) matrice in o (log n) tempo.

Onestamente, io non sono sicuro di come affrontare questo. x dato, posso cercare se esiste in qualsiasi posizione con numero pari usando la ricerca binaria, ma i numeri nelle posizioni dispari non sono più ordinati.

Qualsiasi aiuto è apprezzato. Grazie!

Answer 1

È possibile determinare se alcuni elementi x si trovano nel nuovo set (mescolato) effettuando due ricerche binarie. La chiave qui è che gli elementi dispari agiscono essenzialmente come "chiavi" l'uno per l'altro, dal momento che sono stati scambiati in coppie disgiunte.

1. Utilizzare una ricerca binaria di serie per cercare x, facendo in modo che si sceglie sempre anche indici per il confronto. (Usare gli indici pari è cruciale, perché quelli sono gli elementi che sono ancora in ordine.)

2. Se x è nell'array con un indice pari, sarà trovato. In caso contrario, alla fine troveremo due elementi m e n tali che m < x < n e index(n) - index(m) == 2. Ciò significa che se la matrice è stata ancora ordinata, x dovrebbe essere l'elemento tra m e n (se si trovava nell'array).

3. Considerare l'elemento nell'indice tra m e n - chiamare questo . Se l'elemento x era nell'array originale, deve essere stato scambiato con y durante la creazione dell'array shuffled.

4. Eseguire una seconda ricerca binaria per cercare , assicurandosi di nuovo di scegliere solo indici pari a per il confronto. Analogamente al passaggio 2, alla fine si troveranno due elementi m' e n' tali che m' < y < n' e index(n') - index(m') == 2. Se la matrice è stata ancora ordinata, l'elemento sarebbe l'elemento compreso tra m' e n'.

5. L'elemento tra m' e n' deve essere a seconda di quale elemento è stato scambiato con y, e quindi qualunque elemento era in origine tra il m e n. Se questo valore non è x, allora x non esiste nell'array.