Allora ti spiego la ricerca binaria con un esempio...
Supponiamo ke KEY sia la variabile che contenga il record da ricercare (sicuramente contenuto nel vettore)
Allora supponiamo di avere un array record contenente la sequenza:
3 7 9 28 23 43 54 65
0 1 2 3 4 5 6 7 (indice)
Creiamo due variabili una di nome PRIMO e una di nome ULTIMO, indichiamo rispettivamente il primo e ultimo indice dell' array, per cui PRIMO = 0 e ULTIMO = 7, creiamo un ulteriore variabile MEZZO che sarà uguale a (PRIMO+ULTIMO)/2 ovvero la posizione centrale della sequenza.
Ora se confrontiamo il vettore contenente i record es. record[MEZZO] con KEY otteniamo uno dei seguenti risultati:
__
KEY < record[MEZZO] quindi KEY si troverà sicuramente nella posizione compresa tra 0 e MEZZO -1
Per tanto la Variabile ULTIMO va impostata a MEZZO-1.
__
KEY = record[MEZZO] quindi la funzione restituisce l' indice.
__
KEY > record[MEZZO] quindi KEY si troverà sicuramente nella posizione compresa tra MEZZO +1 e n -1
Per tanto la Variabile PRIMO va impostata a MEZZO+1.
__
L' algero di decisione serve solo a dimostrare l' efficienza dell' algoritmo.
Ora passiamo alla parte pratica:
RICERCA BINARIA RICORSIVA
int confronta(int x, int y){
if(x<y)
return -1;
else if(x==y)
return 0;
else
return 1;
}
int ricercabinaria(int record(),int key.int primo,int ultimo)
{
int mezzo;
if(primo <= ultimo){
mezzo = (primo+ultimo)/2;
switch(confronta(record[mezzo],key)){
case -1: return
ricercabinaria(record,key,mezzo+1,ultimo);
case 0: return mezzo;
case 1: return
ricercabianria(record,key,primo.ultimo-1);
}
}
return -1;
}
Spero di esserti stato di aiuto
Bonny
