/* Ricerca Binaria. Assume che l'array a sia ordinato */
import javax.swing.JOptionPane;

/** Questa classe serve a mostrare il funzionamento dell'algoritmo di ricerca binaria
*/
public class RicercaBinaria
{
	public static void main(String[] args)
	{
		int x;
		int[] a = {10, 12, 15, 16, 25, 29, 46, 47, 48, 67, 68, 72, 73, 85, 93};
		// per semplicita' utilizziamo un array costante, gia' ordinato, sul quale eseguiamo varie ricerche
		
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i]+" ");
		System.out.println();

		x = Integer.parseInt(JOptionPane.showInputDialog("\nInserisci l'elemento da trovare:"));

		// TUTTE LE println SERVONO SOLO A MOSTRARE IL FUNZIONAMENTO DELL'ALGORITMO
		int p, q, m;
		int posizioneTrovata = -1; // se questo valore resta -1 significa che l'elemento non e' stato trovato
		p = 0;
		q = a.length - 1;
System.out.println("valore cercato: " + x);
		while (p <= q && posizioneTrovata == -1)
		{
			m = (p + q) / 2;
System.out.println("intervallo di ricerca: posizioni da "+p + " a " + q);
System.out.printf("posizione mediana: %d, valore %d\n", m, a[m]);
			if (a[m] < x) {
System.out.println("procedo sul secondo semi-intervallo\n");
				p = m + 1;
			}
			else if (a[m] > x) {
System.out.println("procedo sul primo semi-intervallo\n");
				q = m - 1;
			}
			else posizioneTrovata = m;
		}
		// se esco dal ciclo significa che l'intervallo di ricerca si e' ridotto a 0 elementi
		// senza aver trovato il valore el


		if(posizioneTrovata==-1)
			System.out.println("L'elemento "+x+" non e' presente");
		else	
			System.out.println("L'elemento "+x+" e' presente in posizione "+posizioneTrovata);
		System.exit(0);
	}
}