using System;
using System.Diagnostics;
namespace Wyszukiwanie
{
    class Program
    {
        static ulong AddNumberL, AddNumberB;
        long StartingTime = Stopwatch.GetTimestamp();
        bool IsPresentLinInst(ulong[] Vector, ulong Number)
        {
            AddNumberL = 0;
            for (int i = 0; i < Vector.Length; i++, AddNumberL++)
                if (Vector[i] == Number) return true;
            return false;
        }
        bool IsPresentBinInst(ulong[] Vector, ulong Number)
        {
            AddNumberB = 0;
            int Left = 0, Right = Vector.Length - 1, Middle;
            while (Left <= Right)
            {
                AddNumberB++;
                Middle = (Left + Right) / 2;
                if (Vector[Middle] == Number) return true;
                else if (Vector[Middle] > Number) Right = Middle - 1;
                else Left = Middle + 1;
            }
            return false;
        }

        bool IsPresentLinTime(ulong[] Vector, ulong Number)
        {
            for (int i = 0; i < Vector.Length; i++)
                if (Vector[i] == Number) return true;
            return false;
        }
        bool IsPresentBinTime(ulong[] Vector, ulong 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;
        }
        static void Main(string[] args)
        {
            Program mc = new Program();

            /*ulong[] array = new ulong[268435000];
            for (ulong i = 0; i < 268435000; i++)
            {
                array[i] = i;
            }
            //Sprawdzanie wydajności przez instrumentacje
            for (ulong j = 0; j < 268435000; j+= 26843500)
            {
                mc.IsPresentBinInst(array, j);
                mc.IsPresentLinInst(array, j);
                Console.WriteLine(j + " | " + AddNumberL + " | "  + AddNumberB);
            }
            */

            ulong[] array = new ulong[268435000];
            for (ulong i = 0; i < 268435000; i++)
            {
                array[i] = i;
            }
            const int NIter = 10;
            for (ulong u = 0; u < 268435000; u += 26843500)
            {
                double ElapsedSeconds;
                long ElapsedTime = 0, MinTime = long.MaxValue, MaxTime = long.MinValue, IterationElapsedTime;
                for (int n = 0; n < (NIter + 1 + 1); ++n) // odejmujemy wartości skrajne
                {
                    long StartingTime = Stopwatch.GetTimestamp();
                    bool r = mc.IsPresentBinTime(array, u);
                    long EndingTime = Stopwatch.GetTimestamp();
                    IterationElapsedTime = EndingTime - StartingTime;
                    ElapsedTime += IterationElapsedTime;
                    //Console.Write("Iter[" + n + "]:" + IterationElapsedTime + "\t");
                    if (IterationElapsedTime < MinTime) MinTime = IterationElapsedTime;
                    if (IterationElapsedTime > MaxTime) MaxTime = IterationElapsedTime;
                }
                ElapsedTime -= (MinTime + MaxTime);
                ElapsedSeconds = ElapsedTime * (1.0 / (NIter * Stopwatch.Frequency));
                Console.WriteLine("{0}\t{1}", u, ElapsedSeconds.ToString("F4"));
            }

        }
    }
}