Implementazioni di algoritmi/Ricerca dicotomica: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Implementazione in C++ versione non ricorsiva: Aggiornato Etichette: Modifica da mobile Modifica da web per mobile |
|||
Riga 56:
</source>
===Implementazione in [[C++]] versione non ricorsiva===
//#include <vettore.h>
// N.B.: questa implementazione è valida solo se la lista contiene dati numerci (int)
// per estenedere la ricerca ad altri tipi di dati occorre riportare alcune
// modifiche sui tipi di dati e sulle if di comparazione.
/**
@brief ricercaBinariaNonRicorsiva
@param lista vettore in entrata di cui controllare la presenza di X
@param x elemento di cui controllare la presenza
*/
{
int
/**i=posizione iniziale,f=posizione finale,m=posizione media tra iniziale e finale*/
u = n-1;▼
while(p<=u) {▼
Int
/**Definisco la dimensione del vettore*/
if(lista[m]==x) ▼
i =
/**posizione iniziale del vettore*/
p = m+1;▼
else▼
/*Indice in posizione finale del vettore*/
m = (i+f)/2;
return -1;▼
/**faccio la media tra posizione iniziale e finale*/
▲ if(lista[m]==x)
return true;
/**Se trovo il valore restituisco valore true*/
if(lista[m]<x)
/**se l’elemento in posizione m è minore dell’elemento da trovare la posizione di partenza diventa la posizione media del vettore +1 */
▲ else
/**altrimenti (essendo maggiore) la posizione finale diventa la metà-1*/
/**se il programma arriva a questo punto vuol dire che il valore x non è presente in lista, ma se ci fosse,dovrebbe trovarsi alla posizione f (nota che qui i==f)*/
}
//Con questa ricerca riduco il vettore ad ogni test di metà quindi farò al massimo log2(n) tentativi
===Implementazione in [[Java]] versione non ricorsiva===
| |||