[ALGORITMI] Ricerca e sostituzione in array O(log n)

[roinamik]

Ciao, volevo chiedervi in che modo si può implementare un algoritmo che soddisfa le richieste della seguente traccia in tempo O(log n).

Descrivere ed analizzare un algoritmo che presi in input un vettore A[1..n] di interi distinti e un
intero i, 2 ≤ i ≤ n, tale che A[1..i − 1] e’ ordinato in ordine crescente, inserisca A nell’ordine
che gli compete fra i suoi predecessori, ovvero modifichi A in maniera che dopo l’esecuzione
A[1..i] contenga gli stessi elementi di prima, ma in ordine crescente, e i restanti elementi di A
siano immutati. L’algoritmo deve avere una complessita’ di tempo O(logn).


Per esempio: se A[1..6] = [2, 4, 7, 3, 8, 1] ed i = 4, al termine dell’esecuzione il vettore risultante
sara’ A[1..6] = [2, 3, 4, 7, 8, 1].

Grazie mille..

[apatriarca]

Non vedo come possa essere possibile. Anche sapendo esattamente la posizione in cui inserirlo, il solo spostamento di tutti gli elementi successivi (operazione necessaria per inserire un elemento nel mezzo di un array) ha complessità lineare. Immagino supponga quindi che l'inserimento dell'elemento nell'array abbia complessità costante e che la ricerca si possa effettuare utilizzando l'algoritmo di ricerca binaria (ma sinceramente l'unica struttura dati in cui questo credo possa essere possibile è un albero di ricerca binario).

[hamming_burst]

mmm forse se confrontiamo a posizioni logaritmiche tra due step tipo log_2(4) e log_2(8)
se A è > A[log_2(4)] e < A[log_2(8)] sappiamo che dobbiamo riordinare solo questo intervallo (non i successivi).

bho è n'idea di una serata stanca, ma potrebbe esser plausibile.

[apatriarca]

Ma il problema di "far spazio" al nuovo elemento rimane.. Almeno limitandosi al caso degli array.

[hamming_burst]

"apatriarca":Ma il problema di "far spazio" al nuovo elemento rimane.. Almeno limitandosi al caso degli array.

sì in effetti hai ragione.
rimanendo con il mio es. Servirebbe uno schift da es. A[log_2(8)] ad A, dopo aver ordinato l'intervallo.
Nel caso peggiore avrà anche $i=n$ e tanti saluti..

nulla lasciam perdere

[vict85]

Comunque limitandosi alla ricerca si usa, in genere il seguente metodo.

Si prende un elemento i-esimo dell'array (generalmente quello centrale), si vede se l'elemento da inserire è primo o dopo e quindi si procede ricorsivamente nel sottoarray corrispondente.