Genera un array di interi casuali, lo ordina e applica ripetutamente la ricerca binaria
- l’algoritmo di ordinamento è un bubblesort ottimizzato
- Math.random(), genera un numero casuale in [0.0, 1.0[
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
<script> function ordina(array) // bubble sort migliorato { var ultimaCoppia, ultimoScambio, x ultimaCoppia=array.length-2; do { ultimoScambio=0; for(var i=0; i <= ultimaCoppia; i++) { if(parseInt(array[i]) > parseInt(array[i+1])) { x=array[i] array[i]=array[i+1] array[i+1]=x ultimoScambio=i; } } ultimaCoppia=ultimoScambio-1; } while(ultimoScambio > 0); } function ricerca_binaria(array, x) // ricerca binaria { var inf=0, sup=array.length-1 while(inf <= sup) { var medio=Math.floor((inf+sup)/2) if(x < array[medio]) sup=medio-1 else if(x == array[medio]) return medio else inf=medio+1 } return -1 } var maxVal=1000 var quanti=100 document.writeln("<h3>Array di " + quanti + " numeri da 0 a " + (maxVal-1) + "</h3>") var a=new Array(100); for(var i=0; i < quanti; i++) { a[i]=Math.floor(maxVal*Math.random()) document.write(a[i] + " ") } document.writeln("<h3>Ordinato</h3>") ordina(a) for(var i=0; i < quanti; i++) document.write(a[i] + " ") document.writeln("<br/><br/>Scegli il valore e avrai la posizione, <b>-1</b> per uscire<br/>") var ancora var valore do { valore=parseInt(prompt("VALORE? (-1 per uscire)")) if(valore < 0) ancora=false else { ancora=true posizione=ricerca_binaria(a, valore) if(posizione == -1) document.writeln("<br/>" + valore + " <b>non</b> è presente") else document.writeln("<br/>" + valore + " : <b>" + posizione + "</b>") } } while(ancora) </script> |