// ConsoleApplication1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <cstdlib>
/*

1. Pytanie ile elemntow ma miec tablica
2. Pytanie czy tablica ma być losowa czy ręcznie uzupełniona
-> jeżeli ręcznie for z liczbą z pkt 1 i cinem ładujesz
-> jeżeli losowa for z liczbą z pkt 1 i funkcja rand w środku
3. Wypisanie tabeli przed sortowaniem za pomocą fora
4. Wyszukanie liniowe w tabeli (liczba szukana pobierana cinem)
5. Sortowanie tabeli (metoda dowolna)
6. Wyszukanie binarne w tabeli (liczba szukana z punktu 4)

*/
//wyszukanie binarne
//l - lewy index tablicy, p - prawy index tablicy
int i, liczby[20];
int szukaj( int l, int p, long szukana)
{

	while (l <= p)
	{
		liczby[i] = (l + p) / 2;

		if (liczby[i] == szukana)
			return liczby[i];

		if (liczby[i] > szukana)
			p = liczby[i] - 1;
		else
			l = liczby[i] + 1;
	}

	return -1; //zwracamy -1, gdy nie znajdziemy elementu
}



//





int main()
{
	
	int wybor;
poczatek:

	std::cout << "1. Losowe" << std::endl;
	std::cout << "2. Wprowadzone" << std::endl;


	std::cout << "Podaj opcje:" << std::endl;
	std::cin >> wybor;

	switch (wybor)
	{
	case 1:
		std::cout << "1. Liczby losowe" << std::endl;
		goto losowe;

	case 2:
		std::cout << "2. Liczby wpisane" << std::endl;
		goto liczby;

	default:
		std::cout << "Wystapil blad sprobuj ponownie" << std::endl;
		goto poczatek;
		break;
	}



losowe:
	for (int i = 0; i<20; i++)

	{
		liczby[i] = rand() % 60 + 1;
	}
	for (i = 0; i < 20; i++)
	{
		std::cout << liczby[i] << " ";
	}
	goto pomin;
liczby:

	for (int i = 0; i < 20; i++)
	{
		std::cout << std::endl << "Podaj " << i + 1 << " liczby: ";
		std::cin >> liczby[i];
	}

	for (int i = 0; i < 20; i++)
	{
		std::cout << liczby[i] << ", ";

	}

pomin:

	int v, i;

	// odczytujemy poszukiwaną wartość
	std::cout << "Podaj szukany element" << std::endl;
	std::cin >> v;

	// szukamy elementu o wartości v

	for (i = 0; i < 20; i++)
	{
		if (liczby[i] == v) break;
	}

	// wyświetlamy wyniki


		std::cout << std::endl << std::endl;

		if (liczby[i]==v) std::cout << "Element " << v << " na pozycji " << i+1 << std::endl;
		else      std::cout << "Elementu " << v << " nie ma w zbiorze";

		std::cout << std::endl;
		std::cout << "tablica przed posortowaniem: "<<std::endl;
		for (i = 0; i < 20; i++)
		{
			std::cout << liczby[i] << " ";
		}
		std::cout << std::endl;
		//sortowanie babelkowe
		std::cout << "tablica po posortowanu: " << std::endl;
		
		//Wyszukanie binarne 
		
		int zamiana;
		do
		{
			 zamiana = 0;//przed każdym "przejazdem" pętli for zmienna zamiana jest zerowana
			for (int i = 0; i<20; i++)
			{
				if (liczby[i]>liczby[i + 1])// jeśli element tablicy jest większy od następnego elementu
				{
					zamiana = zamiana + 1; //jeśli jest jakaś zmiana, to zmienne zamiana powiększa swoją wartość
					int schowek = liczby[i];//wartość t[i] jest kopiowana do schowka
					liczby[i] = liczby[i + 1];//t[i] przyjmuje wartość następnego elementu, gdyż jest on mniejszy
					liczby[i + 1] = schowek;//kolejny element tablicy przejmuje wcześniejszą wartość poprzedniego elementu, gdyż jest on większy
				}
			}
		} while (zamiana != 0);//jeśli zmienna zamiana miałaby wartość 0, oznaczałoby to że nie dokonano żadnych zmian, a więc nie ma potrzeby dalszego sortowania

		for (int j = 1; j <= 20; j++)
		{
			std::cout << liczby[j] << " ";// wypisanie posortowanych liczb
		}
		
		
		int  szukana;
		
		std::cout << std::endl;
		std::cout << "Podaj jaka liczbe chcesz wyszukac binarnie: " << std::endl;
		std::cin >> szukana;

		for (int i = 0; i<liczby[i]; i++)
		
		std::cout;
		

		int pozycja = szukaj(0, liczby[i] - 1, szukana);

		if (pozycja == -1)
			std::cout << "Liczba " << szukana << " nie wystepuje w zbiorze" <<std::endl;
		else
			std::cout << "Liczba " << szukana << " wystepuje w zbiorze w komorce o numerze " << pozycja << std::endl;
		
		
		
		
		system("pause");
	return 0;

}