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.
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
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
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;
}
}
//#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
/*
* @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
}
/*
* @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
}
}