using System;
using System.Diagnostics;

namespace ConsoleApp6
{
	class Program
	{
		static ulong OpComparisonEQ = 0, OpAssignment = 0, OpComparisonLT = 0, OpIncrement =0;

		//-------------------------------Lin------------------------------
		public static double CheckTimeLin(uint[] Vector, uint Number)
		{

			long StartingTime = Stopwatch.GetTimestamp();

			_IsPresentLinTime(Vector, Number);


			long EndingTime = Stopwatch.GetTimestamp();
			long ElapsedTime = EndingTime - StartingTime;
			double ElapsedSeconds = ElapsedTime * (1.0 / Stopwatch.Frequency);

			return ElapsedSeconds;
		}

		public static bool _IsPresentLinTime(uint[] Vector, uint Number)
		{
			for (int i = 0; i < Vector.Length; i++)
				if (Vector[i] == Number) return true;
			return false;
		}

		public static bool IsPresentLinComp(uint[] Vector, uint Number)
		{
			OpAssignment = OpComparisonLT = 1;
			for (int i = 0; i < Vector.Length; i++, OpIncrement++)
			{
				OpComparisonEQ++;
				if (Vector[i] == Number) return true;
				OpComparisonLT++;
			}
			return false;
		}
			//-------------------------------Bin------------------------------

		public static double CheckTimeBin(uint[] Vector, uint Number)
		{

			long StartingTime = Stopwatch.GetTimestamp();

			_IsPresentBinTime(Vector, Number);

			long EndingTime = Stopwatch.GetTimestamp();
			long ElapsedTime = EndingTime - StartingTime;
			double ElapsedSeconds = ElapsedTime * (1.0 / Stopwatch.Frequency);

			return ElapsedSeconds;
		}

		public static bool _IsPresentBinTime(uint[] Vector, uint Number)
		{
			int Left = 0, Right = Vector.Length - 1, Middle;
			while (Left <= Right)
			{
				Middle = (Left + Right) / 2;
				if (Vector[Middle] == Number) return true;
				else if (Vector[Middle] > Number) Right = Middle - 1;
				else Left = Middle + 1;
			}
			return false;
		}

		public static bool IsPresentBinComp(uint[] Vector, uint Number)
		{
			int Left = 0, Right = Vector.Length - 1, Middle;
			while (Left <= Right)
			{
				Middle = (Left + Right) / 2;
				OpIncrement++;
				if (Vector[Middle] == Number)
					return true;
				else if (Vector[Middle] > Number)
					Right = Middle - 1;
				else
					Left = Middle + 1;
				OpIncrement++;
			}
			return false;
		}

		//-------------------------------Main------------------------------

		static void Main(string[] args)
		{
			double totaltime = 0;
			double avgTime = 0;
			double avgCompare = 0;
			const int loop = 10, startsize = 26843545;

			Console.WriteLine("Linear:");
			Console.WriteLine("Size\tAvgCompare\tAvg.Time[s]\tCompare\tCompare Time[s]\tFound?");

			for (uint size = startsize; size <= (loop * startsize); size += startsize)
			{
				uint[] Tab = new uint[size];

				//uzupełnienie tablicy
				for (uint i = 0; i < Tab.Length; ++i)
				{
					Tab[i] = i;
				}

				//średni czas wyszukiwania
				double tempcomp = 0;
				for (uint i = 1; i < Tab.Length; i += 1000000)//zbieranie co 1000000 elementu w celu przyśpieszenia pomniarów
				{
					totaltime += CheckTimeLin(Tab, i);
					IsPresentLinComp(Tab, i);
					tempcomp++;
				}

				avgCompare = OpIncrement / tempcomp;
				avgTime = totaltime / (size / 100000);
				OpIncrement = 0;

				//pesymistyczne wyniki
				bool znaleziono = IsPresentLinComp(Tab, size);
				double PessymistTime = CheckTimeLin(Tab, size - 1);

				Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", size, avgCompare, avgTime.ToString("F4"), OpIncrement, PessymistTime.ToString("F4"), znaleziono);

			}

			OpIncrement = 0;

			Console.WriteLine("Binary :");
			Console.WriteLine("Size\tAvgCompare\tAvg.Time[s]\tCompare\tCompare Time[s]\tFound?");
			for (uint size = startsize; size <= (loop * startsize); size += startsize)
			{
				uint[] Tab = new uint[size];

				//średni czas wyszukiwania
				for (uint i = 0; i < Tab.Length; ++i)
				{
					Tab[i] = i;
				}

				//liczenie średniego czasu
				for (uint i = 0; i < Tab.Length; ++i)
				{
					totaltime += CheckTimeBin(Tab, i);
					IsPresentBinComp(Tab, i);
				}

				avgTime = totaltime / size;
				avgCompare = OpIncrement / size;
				OpIncrement = 0;
				//pesymistyczne wyniki
				bool znaleziono = IsPresentBinComp(Tab, size);
				double PessymistTime = CheckTimeBin(Tab, size);

				Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", size, avgCompare, avgTime.ToString("F4"), OpIncrement, PessymistTime.ToString("F4"),znaleziono);



			}
		}

	}
}