package esercitazione1;
import java.util.Arrays;
import java.util.Scanner;

public class Esercizio8 {

	public static void main(String[] args) {
		/*
		 * lettura array da input utente
		 */
		Scanner in = new Scanner(System.in);
		System.out.println("Quanti numeri vuoi memorizzare?");
		int n = in.nextInt();
		int[] data = new int[n];
		int i = 0;
		for (; i < n; i++) {
			System.out.println("Inserisci il prossimo numero da memorizzare:");
			data[i] = in.nextInt();
		}
		Arrays.sort(data); // MAGIA: ordiniamo l'array in ordine crescente =)
		// giusto per gli scettici, assicuriamoci che siano ordinati =)
		for (i = 0; i < n; i++) {
			System.out.print(data[i] + " ");
		}
		System.out.println("\nChe numero vuoi cercare?");
		int x = in.nextInt();
		/*
		 * inizio dell'algoritmo di ricerca dicotomica
		 */
		i = 0; // indice che tiene traccia di dove inizia la porzione di array da esaminare
		int f = n - 1; // indice che tiene traccia di dove finisce la porzione di array da esaminare
		int m = 0; // indice per l'accesso al punto medio della porzione di array da esaminare
		boolean found = false;
		while (i <= f) { // se gli indici si invertono singifica che non abbiamo trovato il numero!
			m = Math.round((i + f) / 2); // MAGIA: Math.round(argument) arrotonda argument all'intero più vicino
			if (data[m] == x) {
				found = true;
				break; // basta, abbiamo finito :)
			} else if (data[m] < x) {
				i = m + 1; // se abbiamo beccato un numero inferiore a quello cercato, allora ci concetriamo sulla seconda parte dell'array
			} else {
				f = m - 1; // altrimenti il contrario
			}
		}
		if (found) {
			System.out.println("Trovato! " + x + " compare alla posizione " + m);
		} else {
			System.out.println(x + " non trovato :(");
		}
	}

}