/* genera un array di dimensione letta da tastiera 
 *
 * lo inizializza con interi random tra 0 e 1000000 
 *
 * lo ordina (usando un qualsiasi metodo di ordinamento) 
 *
 * chiede ripetutamente un intero da cercare nell'array e
 * stampa ogni volta il numero di iterazioni eseguite dall'algoritmo
 * di ricerca binaria per trovare l'elemento o per verificarne l'assenza
 */
import java.io.*;
import javax.swing.JOptionPane;
import java.util.Arrays;

public class RicercaBinariaRipetuta
{
	public static void main(String[] args) throws IOException
	{
		int n;
		boolean errore;
		do
		{   errore=true;
			n=0;
/* il costrutto "try" "catch" serve a prevenire interruzioni
 * anomale nel caso di errori durante l'esecuzione (in questo caso
 * possono verificarsi durante la Integer.parseInt quando la 
 * stringa letta non e' numero)
 *
 * La parte "catch" viene eseguita solo quando avviene un errore
 * durante l'esecuzione della parte "try"
 */
			try
			{
				n=Integer.parseInt(JOptionPane.showInputDialog("Digita dimensione del vettore (max 20)"));
				errore=false;
			}
			catch(NumberFormatException e)
			{
				JOptionPane.showMessageDialog(null, "Non hai digitato un numero intero",
				                              "Errore Formato", JOptionPane.WARNING_MESSAGE);
			}
		} while(errore || n<=0);

		int[] v = new int[n];

		for (int i=0; i<v.length; i++)
			v[i] = (int) (1000000 * Math.random());

		Arrays.sort(v);
		
		while(true)
		{
			int x=Integer.parseInt(JOptionPane.showInputDialog("Digita l'intero da cercare (0 per smettere)"));
			if(x==0)
				break;
				
			int p, q, m;
			int nIter=0;
				
			p = 0;
			q = v.length - 1;
			do {
				m = (p + q) / 2;
				if (v[m] < x)
					p = m + 1;
				if (v[m] > x)
					q = m - 1;
				nIter++;
			} while (v[m] != x && p <= q);
			System.out.print(nIter + " iterazioni: ");
			if (v[m] == x)
				System.out.println(x + " trovato in posizione " + m);
			else
				System.out.println(x + " non trovato");
		}
		System.exit(0);
	}
}