using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        const int NIter = 10;
        static int[] TestVector;
        static ulong OpComparisonEQ;
        static bool IsPresent_LinearInstr(int[] Vector, int Number) // Liczba kroków w liniowyn
        {
            for (int i = 0; i < Vector.Length; i++)
            {
                OpComparisonEQ++;
                if (Vector[i] == Number) return true;
            }
            return false;
        }
        static bool IsPresent_LinearTime(int[] Vector, int Number) // czas w liniowym
        {
            for (int i = 0; i < Vector.Length; i++)
                if (Vector[i] == Number)
                    return true;
            return false;
        }
        static bool IsPresent_BinaryInstr(int[] Vector, int Number) // liczba kroków w binarnym
        {
            int Left = 0, Right = Vector.Length - 1, Middle;
            while (Left <= Right)
            {
                OpComparisonEQ++;
                Middle = (Left + Right) / 2;
                if (Vector[Middle] == Number) return true;
                else if (Vector[Middle] > Number) Right = Middle - 1;
                else Left = Middle + 1;
            }
            return false;
        }
        static bool IsPresent_BinaryTime(int[] Vector, int Number) //czas w binarnym
        {
            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;
        }
        static void BinaryAvgInstr() // to co bylo na tablicy
        {
            OpComparisonEQ = 0;
            bool Present;
            for (int i = 0; i < TestVector.Length; ++i)
                Present = IsPresent_BinaryInstr(TestVector, i);
            //Console.Write("\t" + Math.Log(TestVector.Length).ToString("F2"));
            Console.Write("\t" + ((double)OpComparisonEQ / (double)TestVector.Length).ToString("F1"));
        }
        static void LinearMaxInstr() //
        {
            OpComparisonEQ = 0;
            bool Present = IsPresent_LinearInstr(TestVector, TestVector.Length - 1);
            Console.Write("\t" + OpComparisonEQ);
        }
        static void LinearMaxTime()
        {
            double ElapsedSeconds;
            long ElapsedTime = 0, MinTime = long.MaxValue, MaxTime = long.MinValue, IterationElapsedTime;
            for (int n = 0; n < (NIter + 1 + 1); ++n)
            {
                long StartingTime = Stopwatch.GetTimestamp();
                bool Present = IsPresent_LinearTime(TestVector, TestVector.Length - 1);
                long EndingTime = Stopwatch.GetTimestamp();
                IterationElapsedTime = EndingTime - StartingTime;
                ElapsedTime += IterationElapsedTime;
                if (IterationElapsedTime < MinTime) MinTime = IterationElapsedTime;
                if (IterationElapsedTime > MaxTime) MaxTime = IterationElapsedTime;
            }
            ElapsedTime -= (MinTime + MaxTime);
            ElapsedSeconds = ElapsedTime * (1.0 / (NIter * Stopwatch.Frequency));
            Console.Write("\t" + ElapsedSeconds.ToString("F4"));
        }

        static void LinearAvgInstr()
        {
            OpComparisonEQ = 0;
            bool Present = IsPresent_LinearInstr(TestVector, TestVector.Length - 1);
            Console.Write("\t" + ((0.5) + ((double)OpComparisonEQ / 2)));
        }
        static void BinaryMaxInstr()
        {
            OpComparisonEQ = 0;
            bool Present = IsPresent_BinaryInstr(TestVector, TestVector.Length - 1);
            Console.Write("\t" + OpComparisonEQ);
        }
        static void BinaryAvgTim()
        {
            double ElapsedSeconds;
            long ElapsedTime = 0, MinTime = long.MaxValue, MaxTime = long.MinValue, IterationElapsedTime;
            for (int n = 0; n < (NIter + 1 + 1); ++n)
            {
                long StartingTime = Stopwatch.GetTimestamp();
                for (int i = 0; i < TestVector.Length; ++i)
                    IsPresent_BinaryTime(TestVector, i);
                long EndingTime = Stopwatch.GetTimestamp();
                IterationElapsedTime = EndingTime - StartingTime;
                ElapsedTime += IterationElapsedTime;
                if (IterationElapsedTime < MinTime) MinTime = IterationElapsedTime;
                if (IterationElapsedTime > MaxTime) MaxTime = IterationElapsedTime;
            }
            ElapsedTime -= (MinTime + MaxTime);
            ElapsedSeconds = ElapsedTime * (1.0 / (NIter * Stopwatch.Frequency));
            Console.Write("\t" + (ElapsedSeconds / TestVector.Length).ToString("F12"));
        }
        static void BinaryMaxTime()
        {
            double ElapsedSeconds;
            long ElapsedTime = 0, MinTime = long.MaxValue, MaxTime = long.MinValue, IterationElapsedTime;
            for (int n = 0; n < (NIter + 1 + 1); ++n)
            {
                long StartingTime = Stopwatch.GetTimestamp();
                bool Present = IsPresent_BinaryTime(TestVector, TestVector.Length - 1);
                long EndingTime = Stopwatch.GetTimestamp();
                IterationElapsedTime = EndingTime - StartingTime;
                ElapsedTime += IterationElapsedTime;
                if (IterationElapsedTime < MinTime) MinTime = IterationElapsedTime;
                if (IterationElapsedTime > MaxTime) MaxTime = IterationElapsedTime;
            }
            ElapsedTime -= (MinTime + MaxTime);
            ElapsedSeconds = ElapsedTime * (1.0 / (NIter * Stopwatch.Frequency));
            Console.Write("\t" + ElapsedSeconds.ToString("F4"));
        }
        static void LinearAvgTim()
        {
            double ElapsedSeconds;
            long ElapsedTime = 0, MinTime = long.MaxValue, MaxTime = long.MinValue, IterationElapsedTime;
            for (int n = 0; n < (NIter + 1 + 1); ++n)
            {
                long StartingTime = Stopwatch.GetTimestamp();
                for (int i = 0; i < TestVector.Length; ++i)
                    IsPresent_LinearTime(TestVector, i);
                long EndingTime = Stopwatch.GetTimestamp();
                IterationElapsedTime = EndingTime - StartingTime;
                ElapsedTime += IterationElapsedTime;
                if (IterationElapsedTime < MinTime) MinTime = IterationElapsedTime;
                if (IterationElapsedTime > MaxTime) MaxTime = IterationElapsedTime;
            }
            ElapsedTime -= (MinTime + MaxTime);
            ElapsedSeconds = ElapsedTime * (1.0 / (NIter * Stopwatch.Frequency));
            Console.Write("\t" + (ElapsedSeconds / TestVector.Length).ToString("F12"));
        }

        static void Main(string[] args)
        {
            //Console.WriteLine("Size\tMaxI\tMaxT\tAvgI\tBmaxI\tBmaxT\tBavgI\tBavgT");
            Console.WriteLine("Size\tAvgI\tMaxI");
            for (int ArraySize = 26843545; ArraySize <= 268435450; ArraySize += 26843545)
            //for (int ArraySize = 1; ArraySize <= 39; ArraySize += 1) // w sredniej binarce przy 7 elementach powinno wyjsc = 2,43
            {
                Console.Write(ArraySize);
                // -- Create Table
                TestVector = new int[ArraySize];
                // -- Write Table
                for (int i = 0; i < TestVector.Length; ++i)
                {
                    TestVector[i] = i;
                }
                //LinearAvgTim();
                //LinearAvgInstr();
                //LinearMaxInstr();
                //LinearMaxTime();
                //LinearAvgInstr();
                //BinaryMaxInstr();
               // BinaryMaxTime();
               BinaryAvgInstr();
                //BinaryAvgTime();
                Console.Write("\n");

            }
            Console.ReadKey();
        }
    }
}