Esercizio 2
Realizza un programma che dato un vettore di 20 numeri interi compresi fra 1 e 99 generato casualmente (privo di elementi che si ripetono) lo passi ad una funzione assieme ad un intero che deve essere cercato nel vettore.
Usare possibilmente l'algoritmo della ricerca binaria.
La funzione deve restituire la posizione nel vettore dell'elemento cercato, se l'elemento non esiste deve restituire -1.
class ricercaBinaria{
static final int n=20;
public static void main (String[] args){
int i,j,d;
int T[] = new int[n];
//caricamento random senza ripetizioni
for(i=0;i < n;i++)
if(i==0)T[i]=(1 + (int) (Math.random() * 99));
else do{
d=0;
T[i]=(1 + (int) (Math.random() * 99));
for(j=0;j < i;j++)
if(T[i]==T[j])d=1;
}while(d==1);
//cerco il numero 12
System.out.println(binaria(T,12));
//stampa a video
for(i=0;i < n;i++)System.out.print(T[i]+" ");
}//fine main
static int binaria(int T[],int num){
int i,j,x,alto=n-1,basso=0,pos=-1;
//ordinamento
for(i=0;i < n-1;i++)
for(j=i+1;j < n;j++)
if(T[j] <
T[i]){//scambio
x=T[j];
T[j]=T[i];
T[i]=x;
}
// fine if e ordinamento
//ricerca binaria
do{
i=(alto+basso)/2;
if(T[i]==num)pos=i;
else{
if(T[i] < num)basso=i+1;
else alto=i-1;
} //fine else
}while(alto >= basso && pos==-1);
return pos;
}//fine binaria
}//fine class
L'algoritmo per l'ordinamento di scambio è già
stato trattato nel caso dei vettori in C++ .[link]
. Il primo elemento del vettore non richiede controllo.
Quelli estratti successivamente devono essere controllati da un secondo
ciclo
for(j=0;j < i;j++)
if(T[i]==T[j])d=1;
è indispensabile una variabile 'sentinella' d che viene posta a 0 prima
dell'estrazione viene posta a 1 nel caso l'elemento estratto venga riconosciuto
come già estratto durante il controllo; il ciclo viene ripetuto fintanto
che rimane valido quest'ultimo caso.
for(i=0;i < n;i++)
if(i==0)T[i]=(1 + (int) (Math.random() * 99));
else do{
d=0;
T[i]=(1 + (int) (Math.random() * 99));
for(j=0;j < i;j++) if(T[i]==T[j])d=1;
}while(d==1);
La ricerca binaria può essere compresa osservando la seguente illustrazione:
come si può osservare, il vettore deve essere preventivamente ordinato,
la variabile pos viene fissata al valore di default -1 pos=-1
l'indice i assume il valore medio fra alto e basso che all'inizio dell'algoritmo
coincidono coi valori estremi del vettore.
do{
i=(alto+basso)/2;
if(T[i]==num)pos=i;
else{
if(T[i] < num)basso=i+1;
else alto=i-1;
}
}while(alto >= basso && pos==-1);
Si possono presentare solo 3 casi:
1]T[i]=num valore cercato, allora pos assume un valore diverso da -1, e
si esce dal ciclo.
2]T[i] (valore mediano) < num; la variabile basso viene fissata a T[i+1]
e il ciclo viene ripetuto.
3] Altrimenti deve essere T[i] > num,allora la variabile alto viene fissata
a T[i-1] e il ciclo viene ripetuto.
Si va avanti così fino al reperimento del valore cercato oppure finché basso>alto
che vuol dire che il valore non è presente nel vettore.