[C] scemissima domanda sulla ricerca binaria

[cdere]

Salve a tutti,
tramite quest'algoritmo eseguo la ricerca binaria nel mio vettore:
int Dizionario::ricercaBinaria(chiave k)
{
int p,u,m;
p = 0;
u = nPagine-1;
while(p<=u)
{
m = (p+u)/2;
if( dizionario[m].key == k )
return m; // valore k trovato alla posizione m
if( dizionario[m].key < k ) // dizionario[m].key < k
p = m+1;
else
u = m-1;
}
// se il programma arriva a questo punto vuol dire che
// il valore x non è presente nel dizionario, ma se ci fosse
// dovrebbe trovarsi alla posizione u (nota che qui p==u)
return -1; // == false
}

ma adesso, per l'inserimento di un elemento chiave in maniera ordinata, devo implementare un "inserimentoBinario" oppure basta una scansione lineare e da li a spostare tutti gli elementi ?

[fero86]

be', l' "inserimento binario" é piu efficiente, no? entrambe le strade sono fattibili, ma la ricerca lineare della posizione di inserimento ha un costo lineare, quella binaria ha un costo logaritmico.

[cdere]

la ricerca sarà sicuramente binaria, quindi con una complessità logaritmica, e fin qui ci siamo.
Ma per l'inserimentoBinario, mi sai dare una mano?

grazie mille :D

[cdere]

void Dizionario::inserisci(chiave k, attributo a)
{
if( nPagine == 0 )
{
dizionario[0].key = k;
dizionario[0].label = a;
}
else
{
if(k > dizionario[nPagine-1].key)
{
dizionario[nPagine].key = k;
dizionario[nPagine].label = a;
}
else
{
for(int i=0; i<nPagine; i++)
{
if(k < dizionario[i].key)
{
for(int j=nPagine-1; j>=i; j--)
dizionario[j+1]=dizionario[j];
dizionario[i].key = k;
dizionario[i].label = a;
break;
}
}
}
}
nPagine++;
}

ho fatto questa porcheria, qualcuno sa aiutarmi a fare qualcosa di meglio o più efficiente?

[wingman87]

fero86 intendeva che potresti cercare la posizione in cui andrebbe inserito il nuovo elemento con l'algoritmo che hai già scritto (quindi con complessità logaritmica). Poi sposteresti a destra gli elementi per fare spazio al nuovo elemento (e con questo passaggio la complessità "complessiva" diventerà lineare).
L'algoritmo che hai scritto ora mi sembra che abbia complessità quadratica.
EDIT: no, avevo letto male, anche il tuo è lineare, ma manca appunto l'ottimizzazione che suggeriva fero86