/* algoritmo di ricerca binaria
 * (detta anche ricerca dicotomica, o ricerca logaritmica)
 * Si assume che l'array a sia ordinato 
 *
 * Questo algoritmo permette di individuare la posizione di un
 * elemento in un array ordinato, o decidere che l'elemento non è presente,
 * in tempo O(log n) nel caso peggiore, dove n è la dimensione dell'array
 */
 
import java.io.*;

public class RicercaBinaria
{
	public static void main(String[] args) throws IOException
	{
		int inf, sup, med;
		char x;
		char[] a = {'a', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'n', 's'};
		
		System.out.println("L'array contiene i seguenti caratteri:");
		for (int i = 0; i < a.length; i++)
			System.out.print(a[i]);

		System.out.print("\nInserisci l'elemento da trovare: ");
		x = (char) System.in.read(); 
// il metodo System.in.read() legge un carattere da input
// e lo restituisce sotto forma di int (il suo codice ASCII)

		inf = 0;
		sup = a.length - 1;
		System.out.println("inf\tm\tsup");
		do
		{
			med = (inf + sup) / 2;
			System.out.println(inf + "\t" + "\t" + sup);
			System.out.println("\t" + med);
			if (a[med] < x)
				inf = med + 1;
			if (a[med] > x)
				sup = med - 1;
		} while (a[med] != x && inf <= sup);
		if (a[med] == x)
			System.out.println(x + " trovato in posizione " + med);
		else
			System.out.println(x + " non presente");
		System.exit(0);
	}
}