Implementazioni di algoritmi/Ricerca dicotomica

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

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

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

Implementazione in C++ versione non ricorsiva

//#include <vettore.h> // N.B.: questa implementazione è valida solo se la lista contiene dati numerici (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

• /

bool ricercaBinariaNonRicorsiva(vector<int> &lista[], int x) {

  int i,f,m;

/**i=posizione iniziale,f=posizione finale,m=posizione media tra iniziale e finale*/

  Int n=lista.size();

/**Definisco la dimensione del vettore*/

  i = 0;

/**posizione iniziale del vettore*/

  f = n-1; 

/*Indice in posizione finale del vettore*/

      while(I<=f) {

        m = (i+f)/2;

/**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) 
          i = m+1

/**se l’elemento in posizione m è minore dell’elemento da trovare la posizione di partenza diventa la posizione media del vettore +1 */

        else  
          f=m-1;

/**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)*/

  return false;

}

//Con questa ricerca riduco il vettore ad ogni test di metà quindi farò al massimo log2(n) tentativi

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	
}

Implementazione in Java versione 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 ricercaBinariaRicorsiva(int[] lista, int key, int low, int high)

{

        int mid;

        mid = (low + high)/2;

        if (!(mid < low)||(high<0))

        {

                return -1; //Valore non trovato

        }

        else if (key < lista[mid])

        {

                return ricercaBinariaRicorsiva(lista, key, low, mid-1);

        }

        else if (key > lista[mid])

        {

                return ricercaBinariaRicorsiva(lista, key, mid+1, high);

        }

        else

        {

                return mid; //Valore trovato nella posizione mid

        }

}