Giveaway of the Day
AREA RISERVATA
username:
password:
Hai dimenticato la password?
Nessun problema. Inserisci il tuo username e clicca qui.
Il sistema te la invierà nuovamente al primo indirizzo email del tuo profilo.
Non lo hai impostato?
Posso ancora aiutarti. Mandami una email con il tuo username.
La rispedirò al mittente con la password il più presto possibile.
Non sei ancora registrato?
18/03/2012Ricerca dicotomica (o binaria)
Algoritmo di ricerca applicabile su un array ordinato
La ricerca dicotomica, o ricerca binaria, è un algoritmo di ricerca che individua l'indice di un determinato valore presente in un insieme ordinato di dati. La ricerca dicotomica richiede un accesso casuale ai dati in cui cercare (quindi un array).
Questo algoritmo cerca un elemento all'interno di un array ordinato effettuando mediamente meno confronti rispetto ad una ricerca sequenziale, e quindi più rapidamente rispetto ad essa.
La ricerca binaria non usa mai più di [log_2 N] (logaritmo base 2 di N) confronti per trovare (o NON trovare) il valore cercato.
Il principio è quello di iniziare la ricerca non dal primo elemento, ma da quello centrale, cioè inizialmente a metà dell'array. Si confronta questo elemento con quello cercato:
- se corrisponde, la ricerca termina indicando che l'elemento è stato trovato;
- se è inferiore, la ricerca viene ripetuta sulla parte di array che precede l'elemento, scartando tutti quelli successivi;
- se invece è superiore, la ricerca viene ripetuta sulla parte di array successiva all'elemento, scartando tutti quelli precedenti.
Se tutti gli elementi sono stati scartati, la ricerca termina indicando che il valore non è stato trovato.
Si può implementare il processo di ricerca sia con una tecnica lineare che con una ricorsiva. Usando Javascript vediamo entrambi i tipi di implementazione.

var a = new Array( 1, 4, 6, 7, 9, 12, 13, 16, 17, 19, 23, 25, 26, 28 );  //array di valori ordinati

function RicercaNonRicorsiva(valoredacercare) {
  var primo = 0, ultimo = a.length - 1, medio;
  while( primo <= ultimo ) {
    medio = Math.floor((primo + ultimo) / 2);
    if( a[medio] == valoredacercare )
      return medio; // valoredacercare trovato alla posizione medio
    if( a[medio] < valoredacercare ) {
      primo = medio + 1;  // valoredacercare è tra i successivi
    }
    else {
      ultimo = medio - 1;  // valoredacercare è tra i precedenti
    }
  }
  // tutti gli elementi scartati, valoredacercare non c'è
  return -1;
}
alert( RicercaNonRicorsiva(12) );  // mostra 5 (a[5] è l'elemento cercato)
alert( RicercaNonRicorsiva(10) );  // mostra -1 (elemento non trovato)

// questa invece è la versione ricorsiva
function RicercaRicorsiva(valoredacercare, primo, ultimo) {
  if( primo > ultimo )
    return -1;
  var medio = Math.floor((primo + ultimo) / 2);
  if( valoredacercare == a[medio] )
    return medio;
  if( valoredacercare < a[medio] )
    return RicercaRicorsiva(valoredacercare, primo, medio - 1);
  else
    return RicercaRicorsiva(valoredacercare, medio + 1, ultimo);
}
alert( RicercaRicorsiva(12, 0, a.length-1) );
alert( RicercaRicorsiva(10, 0, a.length-1) );
// che mostra gli stessi valori

Sei il visitatore n.  2820511  -  Ci sono  10  utenti in linea in questo momento
2006-2018 pabloNet - pablo@pablonet.it. Questo sito usa i cookie       Ulteriori informazioni

Questo sito usa i cookieACCETTAKOUlteriori informazioni