[Algoritmo] definizione ricerca binaria di un cognome in una lista

[guylmaster]

Ho scritto la definizione di ricerca binaria di un cognome in una lista di cognomi. La lista di cognomi ovviamente è una matrice ed ogni riga rappresenta un cognome.

So di averla scritta malissimo perchè non sono molto bravo a spiegarla, ve la riporto qui e magari mi aiutate a migliorarne l'esposizione?

E' per una relazione, c'ho sprecato abbastanza fatica a fare il programma e non vorrei prendere un burtto voto per la relazione fatta male.

La definizione è la seguente:

Una volta letto il cognome da cercare inizieremo con l’algoritmo di ricerca binaria. Tale metodo di ricerca svolge una serie di prove che consentono di ridurre ripetutamente la porzione della nostra lista di cognomi che può contenere il cognome cercato. Esso può essere paragonato alla ricerca di una pagina in un libro, non si cercherà iniziando nella prima pagina ma si cercherà in una porzione meno vasta del nostro libro che sicuramente conterrà tale pagina. Infatti l’algoritmo di ricerca binaria si calcolerà di volta in volta il centro della nostra lista di cognomi presi in considerazione diminuendo proporzionalmente i cognomi presi in considerazione. Alla fine della nostra ricerca il cognome centrale della nostra lista di cognomi presa in considerazione sarà uguale al cognome cercato altrimenti il cognome non sarà presente nella nostra lista.

Grazie mille in anticipo,
Guylmaster.

[dekdek]

Specifica che l'algoritmo si basa sul fatto che l'array e' ordinato e come cio' influenza la ricerca.
Infatti in un libro qualsiasi saresti obbligato a cercare la pagina desiderata fra tutte, sfogliandole una per una (magari non nell'ordine naturale, ma questo dipende dalla nostra natura umana...)
Se invece cerchi una parola nel dizionaria, allora puoi applicare con successo il metodo dicotomico.

[dekdek]

Stasera scrivo tutto al femminile, chissa' perche'... firuli'.... firula'...

P.S. In realta' e' una scusa per sfoggiare la mia sign...

[Andrea1979]

limitatamente a come hai scritto la definizione/descrizione di ricerca binaria: non è affatto detto che la porzione di lista che stai esaminando contenga la chiave che stai cercando, quanto piuttosto che se la chiave fosse presente nella lista, allora si troverebbe nella porzione che stai esaminando. Come ha già sottolineato dekdek, la ricerca binaria funziona se e solo se la lista su cui esegui la ricerca è stata preventivamente ordinata.

[MMarzia]

attenzione ai titoli: cerchiamo di essere un po' più specifici