Attachment '20130109-Ricerca-array.txt'
Download 1 // RICERCA in array
2 // algoritmi di "ricerca lineare" e "ricerca binaria"
3
4
5 import java.util.*;
6
7 public class RicercaLineareBinaria {
8
9 public static Scanner input = new Scanner(System.in);
10
11 public static void leggiArray(int a[]){
12 System.out.println("Inserire " + a.length + " numeri interi, elementi di un array");
13 for (int i=0; i < a.length; i++)
14 a[i] = input.nextInt();
15 }
16
17 public static void scriviArray(int a[]){
18 for (int i=0; i < a.length; i++)
19 System.out.print( a[i] + " " );
20 System.out.println();
21 }
22
23 public static int ricercaLineare ( int elem, int v[] ) {
24 int nPassi = 0;
25 boolean trovato = false;
26 int i = 0;
27 while(!trovato && i < v.length) {
28 nPassi++;
29 if(v[i] == elem)
30 trovato = true;
31 i++;
32 }
33 System.out.println(" --> numero di passi eseguiti dalla ricerca lineare: " + nPassi);
34 if(trovato)
35 return i-1;
36 return -1;
37 }
38
39 public static int ricercaBinaria (int elem, int v[] ) {
40 int nPassi = 0;
41 int min = 0;
42 int max = v.length-1;
43 int mezzo = (max+min)/2;
44 boolean trovato = false;
45 while(!trovato && min <= max) {
46 nPassi++;
47 mezzo = (max+min)/2;
48 if(v[mezzo] == elem)
49 trovato=true;
50 if(v[mezzo] < elem)
51 min = mezzo + 1;
52 else max = mezzo - 1;
53 }
54 System.out.println(" --> numero di passi eseguiti dalla ricerca binaria: " + nPassi);
55 if(trovato)
56 return mezzo;
57 return -1;
58 }
59
60 public static int ricercaLineareRicorsiva (int elem, int v[], int pos) {
61 if ( pos < 0)
62 return -1;
63 if ( elem == v[pos] )
64 return pos;
65 return ricercaLineareRicorsiva(elem, v, pos-1);
66 }
67
68 public static int ricercaBinariaRicorsiva (int elem, int v[], int inf, int sup) {
69 if( sup < inf )
70 return -1;
71
72 int med = (inf + sup)/2;
73 if (elem == v[med])
74 return med;
75 if (elem < v[med])
76 return ricercaBinariaRicorsiva(elem, v, inf, med-1);
77 return ricercaBinariaRicorsiva(elem, v, med+1, sup);
78 }
79
80
81 public static void main(String[] args) {
82
83 System.out.println(" Inserire un array di numeri interi.");
84 System.out.println(" Quanti elementi conterra' l'array? ");
85
86 int v[] = new int[input.nextInt()];
87 leggiArray(v);
88
89 System.out.println(" Quale elemento si vuole ricercare nell'array? ");
90
91 int elem = input.nextInt();
92
93 int posizione = ricercaLineare(elem,v);
94 if (posizione >= 0)
95 System.out.println("Ricerca lineare: l'elemento " + elem + " si trova in posizione " + posizione);
96 else
97 System.out.println("Ricerca lineare: l'elemento " + elem + " NON e' presente nell'array.");
98
99 posizione = ricercaBinaria(elem,v);
100 if (posizione >= 0)
101 System.out.println("Ricerca binaria: l'elemento " + elem + " si trova in posizione " + posizione);
102 else
103 System.out.println("Ricerca binaria: l'elemento " + elem + " NON e' presente nell'array.");
104
105 posizione = ricercaLineareRicorsiva(elem, v, v.length-1 );
106 if (posizione >= 0)
107 System.out.println("Ricerca lineare ricorsiva: l'elemento " + elem + " si trova in posizione " + posizione);
108 else
109 System.out.println("Ricerca lineare ricorsiva: l'elemento " + elem + " NON e' presente nell'array.");
110
111 posizione = ricercaBinariaRicorsiva(elem, v, 0, v.length-1);
112 if (posizione >= 0)
113 System.out.println("Ricerca binaria ricorsiva: l'elemento " + elem + " si trova in posizione " + posizione);
114 else
115 System.out.println("Ricerca binaria ricorsiva: l'elemento " + elem + " NON e' presente nell'array.");
116 }
117
118 }
Attached Files
You are not allowed to attach a file to this page.