[Algoritmi] Ricerca binaria di un nome

[kikkabis]

Ciao a tutti,
avrei una domanda da farvi.....è possibile sviluppare un algoritmo per la Ricerca Binaria di un nome in un array di nomi??
Come faccio a spostarmi tra i singoli char di ogni nome per fare il confronto?!!Sono un po' confusa

Grazie mille

[apatriarca]

Devi semplicemente sostituire al confronto che fai per esempio sui numeri interi, quello per le stringhe. Usare quindi per esempio strcmp.. Se inserisci del codice possiamo dare qualche consiglio più preciso.

[kikkabis]

Ok, grazie per il consiglio, sto appunto sviluppando il codice, ma mi ero bloccata . Ora provo a proseguire con le tue indicazioni, grazie mille

[Giova411]

Hai mai sentito parlare di ricerca per interpolazione? Magari ti può servire.
Ricordo che era una sorta di "ricerca binaria furba"; quando cerchi un cognome in un elenco telefonico non apri a metà se, ad esempio, il cognome inzia per A o B o C o D.... (Se inizia con queste lettere non ha senso iniziare la ricerca a metà ma, forse, può essere più furbo iniziare a cercare dalla prima metà della metà, quindi a un quarto del numero di pagine)
Ricordo che era O(log (log n)).

[kikkabis]

No, non ne avevo mai sentito parlare...ma è interessante, mi hai incuriosita!Approfondirò questa "ricerca binaria furba"
Grazie mille

[onlyReferee]

Sì, certo. Il consiglio di utilizzare anche la ricerca di interpolazione fornito da Giova411 costituisce un validissimo approfondimento . Questo tipo di ricerca è usato anche nel Data Mining ed è molto importante perché sfrutta meglio anche le informazioni sui valori degli estremi del nostro intervallo di ricerca.