[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

[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