4E SIA: La ricerca lineare, con sentinella, e binaria in C++

 La ricerca lineare, con sentinella, e binaria in C++

In C++ può capitare che abbiamo bisogno di un programma capace di cercare un numero, un carattere, o qualsiasi altro tipo di variabile, all’interno di un array. Per questi problemi esistono 3 tipi principali di algoritmi di ricerca: la ricerca lineare, la ricerca con sentinella, e la ricerca binaria. Ogni ricerca deve essere usata in determinate situazioni.
Ricerca lineare

La ricerca lineare è la più semplice perché confronta tutte le celle dell’array, e attraverso una variabile contatore possiamo contare quante volte il valore cercato si trova nell’array. Di solito questo algoritmo si crea attraverso un ciclo for in questo modo:

1 2 3 4 5 6 7 8 9 10 11 12

//dichiarazione di un array in questo caso riempito dal programmatore int myarray[] {2, 4, 6, 8, 10}; int cont=0, k, cerca; //prendo in input il valore da cercare cout<<"Inserire valore da cercare: "; cin>>cerca; //inizio ciclo for(k=0; k<5; k++) {     if(myarray[k]==cerca)cont++; //incremento il contatore } cout<<"Il valore e' presente "<<cont<<" volte.";

Ricerca con sentinella

La ricerca con sentinella è molto simile a quella lineare. L’unica differenza è che la ricerca con sentinella si usa quando abbiamo un array con valori tutti diversi tra di loro. Si parte dichiarando una variabile booleana impostata su “false”. In questo caso usiamo il ciclo while che confronta ad ogni giro il valore cercato con una cella dell’array. Quando i due valori sono uguali la variabile booleana la impostiamo su “true”, e di conseguenza di esce dal ciclo. Il codice è il seguente:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

//dichiarazione di un array in questo caso riempito dal programmatore int myarray[] {2, 4, 6, 8, 10}; int cerca, k=0; //dichiarazione di una variabile booleana bool b=false; //prendo in input il valore da cercare cout<<"Inserire valore da cercare: "; cin>>cerca; //ripeti il ciclo finche' b e' false e k e' minore di 5 while(b==false && k<5) {     if (myarray[k]==cerca)b=true;     else k++; } //se il valore e' stato trovato if (b==true)cout<<"Il valore e' presente nell'array."; //se il valore non e' stato trovato if (b==false)cout<<"Il valore non e' presente nell'array.";

Ricerca binaria

La ricerca binaria è un tipo di ricerca più complesso. Esso è utilizzabile soltanto quando abbiamo un array di valori ordinati. Il funzionamento consiste nel suddividere l’array in 2 porzioni e verificare in quale delle due parti si trova il numero cercato. L’algoritmo di ricerca binaria usa 3 variabili che indicano all’interno dell’array il primo valore, l’ultimo valore, e il valore centrale della porzione di array che stiamo analizzando. Al primo giro del ciclo la prima variabile sarà impostata a 0, la seconda invece corrisponde alla posizione dell’ultima cifra dell’array. La variabile corrispondente al valore centrale della porzione dell’array viene calcolato invece all’interno del ciclo. In questo modo la ricerca è molto più veloce rispetto alla ricerca lineare e alla ricerca con sentinella, perché invece di confrontare tutti i valori dell’array, ne confronta in questo modo molti di meno. Nell’esempio seguente è presente un array già ordinato, perchè come già detto, è necessario avere un array composto da valori ordinati.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

int myarray[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}; int inf=0, sup=29, m, cerca; bool b = false; //prendo in input il valore da cercare cout<<"Inserire valore da cercare: "; cin>>cerca; while(b==false && inf<=sup) {     m=(inf+sup)/2;     if (cerca==myarray[m] || cerca==myarray[inf] || cerca==myarray[sup]) b=true;     else     {         if (cerca<myarray[m])         {             inf++;             sup=m-1;         }         else         {             inf=m+1;             sup--;         }     }     npassaggi++; } //se il valore e' stato trovato if (b==true)cout<<"Il valore e' presente nell'array."; //se il valore non e' stato trovato if (b==false)cout<<"Il valore non e' presente nell'array.";

In questo esempio, se noi volessimo cercare il numero 19 all’interno dell’array, lo troveremmo alla posizione 18. Se noi avessimo cercato questo numero con l’algoritmo della ricerca con sentinella, l’elaboratore avrebbe eseguito 18 confronti prima di trovare il numero. Con l’algoritmo della ricerca binaria, cercare il numero 19, comporta soltanto 3 passaggi.

fonte: http://michelangeloprogramming.altervista.org/la-ricerca-lineare-con-sentinella-e-binaria-in-c/?doing_wp_cron=1673859686.5087010860443115234375