import java.util.Scanner;

public class main {
		public static void main(String[] args) {

		Scanner sc= new Scanner(System.in); //Scannera bedziemy potrzebowac do zeskanowania liczby z klawiatury
		int [] a=new int [] {5, 3, 7, 4, 1, 8, 2}; //Inicjowanie tablicy
		System.out.println("Tablica przed sortowaniem: ");
		for(int i=0; i<a.length; i=i+1) //wypisanie tablicy przed posortowaniem
			System.out.println(a[i]+" ");
		sortowanieBabelkowe(a);  //uzycie sortowania
		System.out.println("\n Tablica po sortowaniu: ");
		for(int i=0; i<a.length; i=i+1)  //wypisanie tablicy po posortowaniem
			System.out.println(a[i]+" ");
		System.out.println("Podaj liczbe którą chcesz wyszukac");
		int liczba=sc.nextInt();  //przypisanie scannera do zmiennej
		if(wyszukiwanieBinarne(a,liczba)==-1)  //Sprawdzenie czy wyszukiwanie znalazlo liczbe
			System.out.println("Liczba nie znajduje się w tablicy"); // jesli wynik wyszedł -1 oznacza to że nie ma liczby w tablicy
		else  //Kazdy inny przypadek to numer indeksu na ktorym jest liczba
			System.out.println("Liczba znajduje się w tablicy na miejscu: "+(wyszukiwanieBinarne(a,liczba)+1));
		}

		static void sortowanieBabelkowe(int[] b){ //sortowanie
		int i; int k; int buf;
		for(k=b.length-1; k>0; k=k-1) //gorna petla po wszystkich elementach od lewej do prawej
			for(i=0; i<k; i=i+1) // dolna petla bioraca wszystkie elementy z prawej
				if(b[i] > b[i+1]){ //sprawdzenie czy liczba jest mniejsza i ewentualna zamiana
					buf=b[i]; //przypisanie zeby nie zgubic aktualnej liczby
					b[i]=b[i+1]; //zamiana
					b[i+1]=buf; //zamiana
			}
		}

		static int wyszukiwanieBinarne(int[] tablica, int klucz){
	        int dol = 0; //poczatek naszej tablicy
	        int gora = tablica.length - 1; //koniec naszej tablicy
	        while (dol <= gora) { //warunek zakonczenia petli jesli nasza tablica jest minimalnego rozmiaru
	            int srodek = dol + (gora - dol) / 2; //srodek tablicy obliczony ze sredniej
	            if      (klucz < tablica[srodek]) gora = srodek - 1; //jesli szukana liczba jest mniejsza niz srodkowy element tablicy to zmniejszamy nasza tablice o polowe w dol
	            else if (klucz > tablica[srodek]) dol = srodek + 1; //jesli szukana liczba jest wieksza niz srodkowy element tablicy to
	            //zmniejszamy naszą tablice do polowy ale idziemy do drugiej połówki(tej większej)
	            else return srodek; //zwracamy indeks liczby której szukaliśmy i wychodzimy z wyszukiwania
	        }
	        return -1; //petla nie znalazla naszej liczby wiec zwracamy wartosc ujemna(dziala jesli w tablicy nie ma wartosci ujemnych)
	    }

}