/* 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:"));

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

/** Metodo principale: implementa l'algoritmo di ricerca binaria.
Dati come parametri un array di int, ordinato in senso non decrescente, e un
valore int, restituisce la posizione in cui compare il valore nell'array. Se l'array non
contiene il valore cercato viene restituita la posizione convenzionale -1.
@param v l'array ordinato in senso non decrescente in cui effettuare la ricerca
@param el il valore da cercare
@return la posizione di una occorrenza dell'elemento el nell'array v. Se non esiste nessuna
occorrenza il metodo restituisce -1.
*/
	public static int ricercaBinaria(int[] v, int el)
	{
		// TUTTE LE println SERVONO SOLO A MOSTRARE IL FUNZIONAMENTO DELL'ALGORITMO
		int p, q, m;
		p = 0;
		q = v.length - 1;
		while (p <= q)
		{
			m = (p + q) / 2;
System.out.println("intervallo di ricerca: posizioni da "+p + " a " + q);
System.out.println("posizione mediana: " + m);
			if (v[m] < el) {
System.out.println("procedo sul secondo semi-intervallo\n");
				p = m + 1;
			}
			else if (v[m] > el) {
System.out.println("procedo sul primo semi-intervallo\n");
				q = m - 1;
			}
			else return m;
		}
		// se esco dal ciclo significa che l'intervallo di ricerca si e' ridotto a 0 elementi
		// senza aver trovato il valore el
		return -1;
	}
}