# Informatica 2 Liceo Scientifico Scienze Applicate/Ricerca Dicotomica

Informatica 2 Liceo Scientifico Scienze Applicate
Copertina Tutti i moduli · Sviluppo
* Linguaggi di programmazioneInformatica 2 Liceo Scientifico Scienze Applicate/Linguaggi di programmazione
* Compilare un programmaInformatica 2 Liceo Scientifico Scienze Applicate/Compilare un programma
* CiaoMondoInformatica 2 Liceo Scientifico Scienze Applicate/CiaoMondo
* AreaRettangoloInformatica 2 Liceo Scientifico Scienze Applicate/AreaRettangolo
* AreaTrapezioInformatica 2 Liceo Scientifico Scienze Applicate/AreaTrapezio
** Compito1Informatica 2 Liceo Scientifico Scienze Applicate/Compito1
* Programmazione ImperativaInformatica 2 Liceo Scientifico Scienze Applicate/Programmazione Imperativa
* Diagrammi di FlussoInformatica 2 Liceo Scientifico Scienze Applicate/Diagrammi di Flusso
* Operatori AritmeticiInformatica 2 Liceo Scientifico Scienze Applicate/Operatori Aritmetici
* Istruzione ifInformatica 2 Liceo Scientifico Scienze Applicate/Istruzione if
** Esercizio Equazione 2^ gradoInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio Equazione 2^ grado
** Esercizio Calcola lo ScontoInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio Calcola lo Sconto
** Esercizio Calcola lo Sconto2Informatica 2 Liceo Scientifico Scienze Applicate/Esercizio Calcola lo Sconto2
* Operatori LogiciInformatica 2 Liceo Scientifico Scienze Applicate/Operatori Logici
** Esercizio x interno all'intervalloInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio x interno all'intervallo
** Esercizio x esterno all'intervalloInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio x esterno all'intervallo
* Istruzione switchInformatica 2 Liceo Scientifico Scienze Applicate/Istruzione switch
** Esercizio Scelta EquazioneInformatica 2 Liceo Scientifico Scienze Applicate/Esercizio Scelta Equazione
* Altre Istruzioni di Scelta o DiramazioneInformatica 2 Liceo Scientifico Scienze Applicate/Altre Istruzioni di Scelta o Diramazione
* Istruzioni di RipetizioneInformatica 2 Liceo Scientifico Scienze Applicate/Istruzioni di Ripetizione
** Es (do-while) Indovina il numeroInformatica 2 Liceo Scientifico Scienze Applicate/Es (do-while) Indovina il numero
** Es (while) La nonna è stancaInformatica 2 Liceo Scientifico Scienze Applicate/Es (while) La nonna è stanca
** Es (for) Somma di 5 numeriInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Somma di 5 numeri
** Es (for) Analisi sequenza datiInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Analisi sequenza dati
** Es (for) Sequenze NumericheInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Sequenze Numeriche
** Es (for) SupermarketInformatica 2 Liceo Scientifico Scienze Applicate/Es (for) Supermarket
** Es (while) Bisca ClandestinaInformatica 2 Liceo Scientifico Scienze Applicate/Es (while) Bisca Clandestina
* Compito2Informatica 2 Liceo Scientifico Scienze Applicate/Compito2
* I vettoriInformatica 2 Liceo Scientifico Scienze Applicate/I vettori
** Es Usiamo i vettoriInformatica 2 Liceo Scientifico Scienze Applicate/Es Usiamo i vettori
** Es2 Usiamo i vettoriInformatica 2 Liceo Scientifico Scienze Applicate/Es2 Usiamo i vettori
** Es3 Supermarket con vettoriInformatica 2 Liceo Scientifico Scienze Applicate/Es3 Supermarket con vettori
** Compito dic 2019Informatica 2 Liceo Scientifico Scienze Applicate/Compito dic 2019
** BubbleSortInformatica 2 Liceo Scientifico Scienze Applicate/BubbleSort
** Ricerca DicotomicaInformatica 2 Liceo Scientifico Scienze Applicate/Ricerca Dicotomica
* Matrici e ArrayInformatica 2 Liceo Scientifico Scienze Applicate/Matrici e Array
** Es matrici battaglia navaleInformatica 2 Liceo Scientifico Scienze Applicate/Es matrici battaglia navale
** Es matrici 1Informatica 2 Liceo Scientifico Scienze Applicate/Es matrici 1
** Es matrici 2Informatica 2 Liceo Scientifico Scienze Applicate/Es matrici 2
* PuntatoriInformatica 2 Liceo Scientifico Scienze Applicate/Puntatori
* StructInformatica 2 Liceo Scientifico Scienze Applicate/Struct
** Es Bubble Sort con StructInformatica 2 Liceo Scientifico Scienze Applicate/Es Bubble Sort con Struct
* FunzioniInformatica 2 Liceo Scientifico Scienze Applicate/Funzioni
* Funzioni Void e non VoidInformatica 2 Liceo Scientifico Scienze Applicate/Funzioni Void e non Void
** esercizi1 funzioniInformatica 2 Liceo Scientifico Scienze Applicate/esercizi1 funzioni
** esercizi2 funzioniInformatica 2 Liceo Scientifico Scienze Applicate/esercizi2 funzioni
** esercizi3 funzioniInformatica 2 Liceo Scientifico Scienze Applicate/esercizi3 funzioni
* BacktrackingInformatica 2 Liceo Scientifico Scienze Applicate/Backtracking
* TemplateInformatica 2 Liceo Scientifico Scienze Applicate/Template
* FileInformatica 2 Liceo Scientifico Scienze Applicate/File
** File di TestoInformatica 2 Liceo Scientifico Scienze Applicate/File di Testo
** File BinariInformatica 2 Liceo Scientifico Scienze Applicate/File Binari
** File RecordsInformatica 2 Liceo Scientifico Scienze Applicate/File Records
** Es FilesInformatica 2 Liceo Scientifico Scienze Applicate/Es Files
* Esercizi VacanzeInformatica 2 Liceo Scientifico Scienze Applicate/Esercizi Vacanze
** Esercizi1Informatica 2 Liceo Scientifico Scienze Applicate/Esercizi1
** Esercizi2Informatica 2 Liceo Scientifico Scienze Applicate/Esercizi2
** Esercizi3Informatica 2 Liceo Scientifico Scienze Applicate/Esercizi3
* Olimpiadi Informatica
** NobileChimicoInformatica 2 Liceo Scientifico Scienze Applicate/NobileChimico
** Sunnydale
** MappaAnticaInformatica 2 Liceo Scientifico Scienze Applicate/MappaAntica
Modifica il sommario

## Ricerca Dicotomica o Ricerca Binaria o Ricerca per Bisezione

La ricerca dicotomica e' la tecnica piu' veloce O(log$_2$(n)) per ricercare un elemento in un vettore ordinato, e se lo trova ne restituisce la posizione. Se il vettore non è ordinato si utilizza una ricerca esaustiva che risulta però molto piu lenta ( mediamente se trovato O(n/2), se non presente O(n) ).
Nella ricerca dicotomica si parte dal vettore ordinato, e da due indici inf e sup che ne delimitano l'intervallo di ricerca, di solito inizialmente inf=0 e sup=n-1 se il vettore ha n elementi, e dal numero ricercato.
Si prende la cella centrale del vettore che ha indice centro=(inf+sup)/2, la divisione e' fra interi e restituisce l'indice della cella centrale o quella della cella che la precede. Se siamo fortunati troviamo nella cella centrale il valore ricercato, altrimenti bisogna proseguire la ricerca, determinando un nuovo intervallo di ricerca
* se valorericercato e' minore del valore della cella centrale pari a vett[centro]
* se valorericercato e' maggiore del valore della cella centrale pari a vett[centro]
e poi si ripete il procedimento applicandolo al nuovo intervallo di ricerca.
Si termina l'algoritmo in due situazioni
Il metodo usato e' molto veloce perché se nella posizione centrale non trovo il numero ricercato la successiva ricerca e' condotta solo nella parte inferiore (escludendo cosi'meta' delle celle, cioe' la parte superiore e la cella centrale) o solo la parte superiore (escludendo cosi'meta' delle celle, cioe' la parte inferiore e la cella centrale) dell'intervallo considerato.
Pensiamo a un vocabolario di 10000 pagine, in cui ad ogni pagina corrisponde una sola parola, le parole del vocabolario sono ordinate in senso alfabetico, pensiamo di dover ricercare una parola, individuiamo la pagina centrale, se in quella pagina c'e' la parola cercata siamo fortunati e abbiamo risolto il problema, altrimenti se la parola ricercata e maggiore in senso alfabetico di quella ricercata continuiamo la ricerca nella parte superiore del libro eliminendo così la parte inferiore del libro (500 pagine) e la pagina centrale, altrimenti continuiamo la ricerca nella parte inferiore eliminando le pagine superiori(500+pagina centrale). Ora in un solo passo abbiamo dimezzato le pagine su cui continuare la ricerca. Ci sono rimaste 499 pagine, troviamo la pagina centrale, se siamo fortunati troviamo su quella pagina la parola ricercata, altrimenti continuiamo la ricerca o nelle 249 pagine superiori o inferiori, ad ogni passo le pagine rimaste si riducono della meta', alla fine se siamo stati sfortunati ci e' rimasta una sola pagina sulla quale o c'e' la parola ricercata oppure non c'e' (l'intervallo di ricerca si e' allora esaurito)
per calcolare il numero di passi massimo che dobbiamo fare per determinare la posizione della pagina se c'e' o per capire che quella parola non esiste nel nostro vocabolario/vettore si deve calcolare il log$_2$(n) dove n e' il numero di elementi del vettore .
Vediamo un esempio pratico, si ricerca il numero 21 in un vettore composto da 18 elementi, inf=0 e sup=17
calcoliamo l'indice della cella centrale dell'intervallo 0-17 centro=(inf+sup)/2 = (0+17)/2= 8 , la formula se sono rimaste un numero pari di celle prende fra le due celle centrali quella di indice minore, se il numero di celle e' dispari il problema non si pone.
In questo caso vett[centro]=vett[8]=34 e siamo sfortunati, visto che 21<34 bisogna continuare nella parte inferiore dell'intervallo (rispetto alla posizione centro) scartando tutte le celle con i valori da 34 a 123,
il nuovo intervallo di ricerca mantiene il valore di inf (che era 0) e pone sup=centro-1=7; le celle eliminate sono quelle in giallo e quella in rosso
si determina il nuovo indice centrale dell'intervallo inf=0 sup=7 si ha centro=(inf+sup)/2 = 3, siamo nuovamente sfortunati, cerchiamo il valore 21, ma nella cella centrale vett[3] c'e' il numero 9, visto che 21>9 si continua la ricerca nella parte superiore
spostiamo inf al valore centro+1 ora inf=4 e manteniamo sup (che era 7), vengono escluse cosi' le celle con i valori da 2 a 9
si determina il nuovo indice centrale dell'intervallo inf=4 sup=7 si ha centro=(inf+sup)/2 = 5, siamo nuovamente sfortunati, cerchiamo il valore 21, ma nella cella centrale vett[centro]=vett[5] c'e' il numero 14, visto che 21>14 si continua la ricerca nella parte superiore
spostiamo inf al valore centro+1 ora inf=6 e manteniamo sup (che era 7), vengono escluse cosi' le celle con i valori da 11 a 14
si determina il nuovo indice centrale dell'intervallo inf=6 sup=7 si ha centro=(inf+sup)/2 = 6, finalmente!!! abbiamo trovato il numero 21 si trova nella posizione centro=6 e l'algoritmo della ricerca dicotomica termina potendo restituire la posizione del numero 21 all'interno del vettore
se il numero da ricercare fosse stato 22 invece di 21 allora avremmo avuto gli stessi passaggi visti prima e ora si avrebbe
si determina il nuovo indice centrale dell'intervallo inf=6 sup=7 si ha centro=(inf+sup)/2 = 6, siamo nuovamente sfortunati, cerchiamo il valore 22, ma nella cella centrale vett[centro]=vett[6] c'e' il numero 21, visto che 22>21 si continua la ricerca nella parte superiore
spostiamo inf al valore centro+1 ora inf=7 e manteniamo sup (che era 7), viene esclusa cosi' la cella con il valore 21
si determina il nuovo indice centrale dell'intervallo inf=6 sup=7 si ha centro=(inf+sup)/2 = 7, siamo nuovamente sfortunati, cerchiamo il valore 22, ma nella cella centrale vett[centro]=vett[7] c'e' il numero 23, visto che 22<23 si continua la ricerca nella parte inferiore (abbiamo appena scartato l'ultima cella rimasta spostando uno dei due indici l'intervallo di ricerca non e' piu' valido perché inf>sup)
spostiamo sup al valore centro-1 ora sup=6 e manteniamo inf (che era 7) l'algoritmo termina non avendo piu' un intervallo di ricerca valido, infatti l'estremo inferiore e' diventato piu' grande di quello superiore, questo significa che non siamo riusciti a trovare il numero cercato (22) nel vettore
L'algoritmo in C per fare una ricerca dicotomica su un vettore e' allora
E un programma complessivo con l'inserimento dei dati, ordinamento e ricerca dicotomica e' il seguente