Implementazioni di algoritmi/Ricerca dicotomica

Wikibooks, manuali e libri di testo liberi.

Sommario
Categoria · Copertina · Sviluppo · modifica il template

Copertina Implementazioni di algoritmi/Copertina

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.

Indice

[modifica] Implementazione in Python versione ricorsiva

def binsearchr(seq, search, left=0, right=None):    
  if right==None: right = len(seq)
  center = (left + right) / 2
  if left>right:
    return -1
  if search<seq[center]:
    return binsearchr(seq, search, left, center-1)
  elif search>seq[center]:
    return binsearchr(seq, search, center+1, right)
  else:
    return center

[modifica] Implementazione in Python versione non ricorsiva

def binsearch(seq, search):
  left = 0
  right = len(seq)-1
  while left<=right:
    center = (left + right) / 2
    if search<seq[center]:
      right=center-1
    elif search>seq[center]:
      left=center+1
    else:
      return center
  return -1

[modifica] Implementazione in C versione ricorsiva

 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;
    }
 
 }

[modifica] Implementazione in C versione non ricorsiva

// lista l'array su cui effettuare la ricerca
// n     numero elementi della lista
// x     chiave da ricercare
// 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.
//       buon lavoro!
 
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;
}

[modifica] Implementazione in Java versione non ricorsiva

/*
 * @param lista l'array ordinato su cui effettuare la ricerca
 * @param key il valore da cercare
 * @return la posizione del valore trovato, -1 se non l'ha trovato
*/
public int ricercaBinariaNonRicorsiva(int lista[], int key)
{
	int low = 0;
	int high = lista.length-1;
 
	while (low<=high) {
		int mid = (low+high)/2;
		if(lista[mid]==key)) {
			return mid; //valore trovato nella posizione mid
	        }
		else if (lista[mid]<key) {
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
	return -1; //non l'ha trovato	
}

Ricavato da "http://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Ricerca_dicotomica"
Strumenti personali