#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;

bool IsNumberNatural(int UpperLimit, int number)
{
	if (UpperLimit > number)
	{
		return false;
	}
	else
	{
		return true;
	}
}

void CreateArray(int* Arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		Arr[i] = rand() % 100;
	}
}

void DisplayArray(int* Arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << Arr[i] << " ";
	}
}

int LinearSearch(int *Arr, int n, int search)
{
	for (int i = 0; i < n; i++)
	{
		if (Arr[i] == search) return i;
	}
	return -1;
}

int BinarySearch(int *Arr, int n, int search)
{
	int left(0), right(0), mid(0);
	left = 0; right = n - 1;

	while (left <= right)
	{
		mid = (left + right) / 2;
		if (Arr[mid] == search)
		{
			return mid;
		}
		else if (search < Arr[mid])
		{
			right = mid - 1;
		}
		else if (search > Arr[mid])
		{
			left = mid + 1;
		}
	}
	return -1;
}

int main()
{
	srand(time(NULL));
	int n(0), l(0), choice(0), search(0), position(0), position2(0);
	cout << "Podaj rozmiar tablicy: ";
	cin >> n;
	while (!IsNumberNatural(0, n))
	{
		cout << "Rozmiar tablicy musi byc dodatni. Podaj rozmiar ponownie: ";
		cin >> n;
	}
	int* Arr = new int[n];

	cout << "Podaj ilosc eksperymentow laboratoryjnych (optimum: 5): ";
	cin >> l;
	cout << "Wybierz typ wyszukiwania (1-lokalne, 2-binarne): ";
	cin >> choice;
	cout << "Jaka liczbe chcesz znalezc?: ";
	cin >> search;

	switch (choice)
	{
	case 1:
	{
		for (int a = 0; a < l; a++)
		{
			CreateArray(Arr, n);
			DisplayArray(Arr, n);
			cout << "\n";
			position = LinearSearch(Arr, n, search);
			if (position != -1)
				cout << "Element " << search << " zostal znaleziony na pozycji " << position + 1;
			else
				cout << "Element " << search << " nie zostal znaleziony";
			cout << "\n";
		}
		cout << "\n";
		break;
	}
	case 2:
	{
		for (int a = 0; a < l; a++)
		{
			CreateArray(Arr, n);
			DisplayArray(Arr, n);
			cout << "\n";
			position2 = BinarySearch(Arr, n, search);
			if (position2 != -1)
				cout << "Element " << search << " zostal znaleziony na pozycji " << position2 + 1;
			else
				cout << "Element " << search << " nie zostal znaleziony";
			cout << "\n";
		}
		cout << "\n";
		break;
	}
	default:
	{
		cout << "Wybor spoza wykresu!";
		break;
	}
	}
	system("PAUSE");
	return 0;
}