Implementazioni di algoritmi/Ricerca dicotomica: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nuova pagina: {{implementazioni di algoritmi}} ===Implementazione in Python=== <source lang="python"> def binsearch(seq, search): right = len(seq) left = 0 previous_center = -1 i... |
cambio avanzamento a 100% |
||
Riga 1:
{{implementazioni di algoritmi}}
La '''ricerca dicotomica''' (o ricerca binaria) è un algoritmo di ricerca per individuare un determinato valore all'interno di un insieme ordinato di dati. La ricerca dicotomica richiede un accesso casuale ai dati in cui cercare.
===Implementazione in [[Python]]===
<source lang="python">
Line 20 ⟶ 21:
left = center
previous_center = center
</source>
===Implementazione in [[C]]===
<source lang="c">
int ricercaBinaria(int lista[], int x, int a, int z ) {
int m;
// Determina l'elemento centrale
m = ( a + z ) / 2;
if ( m < a || z < 0 ) {
// l'elemento cercato non c'è
return -1;
} else if ( x < lista[m] ) {
// Si ripete la ricerca nella parte inferiore
return ricercaBinaria( lista, x, a, m-1 );
} else if ( x > lista[m] ) {
// Si ripete la ricerca nella parte superiore
return ricercaBinaria( lista, x, m+1, z );
} else {
// m rappresenta l'indice dell'elemento cercato
return m;
}
}
</source>
<source lang="c">
int ricercaBinariaNonRicorsiva(int lista[], int n, int x)
{
int p,u,m;
p = 0;
u = n-1;
while(p<=u) {
m = (p+u)/2;
if(lista[m]==x)
return m; // valore x trovato alla posizione m
if(lista[m]<x)
p = m+1;
else
u = m-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 u (nota che qui p==u)
return -1;
}
</source>
[[Categoria:Implementazioni di algoritmi|Ricerca dicotomica]]
{{Avanzamento|
| |||