/* 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 int immettiIntero(String messaggio, int min, int max)
	{
		boolean errore;
		int n=0;
		do
		{   errore=true;
/* 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(messaggio));
				errore=false;
			}
			catch(NumberFormatException e)
			{
				JOptionPane.showMessageDialog(null, "Non hai digitato un numero intero",
				                              "Errore Formato", JOptionPane.WARNING_MESSAGE);
			}
		} while(errore || n<min || n>max);
		return n;	
	}


	
	public static int RicercaBinaria(int[] v, int el)
	{
		int p, q, m;
		p = 0;
		q = v.length - 1;
		while (p <= q)
		{
			m = (p + q) / 2;
			if (v[m] < el)
				p = m + 1;
			else if (v[m] > el)
				q = m - 1;
			else return m;
		}
		if (v[p] == el)
			return p;
		else
			return -1;
	}

	public static void main(String[] args) throws IOException
	{
		int n;
		n=immettiIntero("Digita dimensione del vettore (max 300)", 1, 300);

		int[] v = new int[n];

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

		Arrays.sort(v);
		
		for(int i=0; i<v.length; i++)
			System.out.print(" "+v[i]);
		System.out.println();
		while(true)
		{
			int x=immettiIntero("Digita intero da cercare (tra 0 e 999, -1 per smettere)", -1, 999);
			if(x==-1)
				break;
				
			int posizione=RicercaBinaria(v, x);
			if (posizione == -1)
				System.out.println(x + " non trovato");
			else
				System.out.println(x + " trovato in posizione " + posizione);
		}
		System.exit(0);
	}
}