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

namespace ALgorytmy_projekt1
{
    class Program
    {
        const int rozmiar = 268435456;
        static int[] Tab;
        static long LicznikOperacji;

        static int WyszukajLiniowo(int wektor, int liczba)
        {

            for (int i = 0; i < wektor; i++)
            {
                LicznikOperacji++;
                if (Tab[i] == liczba) return i;
            }
            return -1;
        }
    
        static void WyszLinPes()
        {
            Stopwatch stoper = new Stopwatch();
            for (int i = 1; i <=10000; i+=100)
            {
                int x = i;
                LicznikOperacji = 0;
                stoper.Start();
                WyszukajLiniowo(x, 0);
                stoper.Stop();
                Console.WriteLine("{0}| {1}| {2}", x, LicznikOperacji, stoper.ElapsedMilliseconds);
                stoper.Reset();
            }
        }

        static void WyszLinSre()
        { Stopwatch stoper = new Stopwatch();
            
            for (int i = 0; i <= 10000; i +=100)
            {
                int x = i;
                LicznikOperacji = 0;
                for (int j = 0; j < x; j++)
                {
                    stoper.Start();
                    WyszukajLiniowo(x, Tab[j]);
                    stoper.Stop();
                }   
                Console.WriteLine("{0}| {1}| {2}", x, (((1.0*LicznikOperacji))/x),stoper.ElapsedMilliseconds);
                stoper.Reset();
            }
        }

        static int WyszukajBinarnie(int wektor, int liczba)
        {
            int Left = 0;
            int Right = wektor - 1;
            int Middle;
            while (Left <= Right)
            {
                LicznikOperacji++;
                Middle = (Left + Right) / 2;
                if (Tab[Middle] == liczba) return Middle;
                else if (Tab[Middle] > liczba) Right = Middle - 1;
                else Left = Middle + 1;
            }
            return -1;
        }

        static void WyszBinPes()
        {
            Stopwatch stoper = new Stopwatch();
            for (int i = 1; i <= 28; i++)
            {
                int n = (1 << i);
                LicznikOperacji = 0;
                stoper.Start();
                WyszukajBinarnie(n, 0);
                stoper.Stop();
               
                Console.WriteLine("{0}| {1}| {2}", n, LicznikOperacji,stoper.ElapsedMilliseconds);
                stoper.Reset();
            }
        }

        static void WyszBinSre()
        {
            Stopwatch stoper = new Stopwatch();
            for (int i = 1; i <= 28; i++)
            {
                int n = (1 << i);
                LicznikOperacji = 0;
                for (int j = 0; j < n; j++)
                {
                    stoper.Start();
                    WyszukajBinarnie(n, Tab[j]);
                    stoper.Stop();
                }
                Console.WriteLine(" {0}| {1}| {2}", n,((1.0*LicznikOperacji)/n),stoper.ElapsedMilliseconds);
                stoper.Reset();
            }
            
        }
        static void Main(string[] args)
        {
            Tab = new int[rozmiar];
            for (int i = 0; i < rozmiar; i++)
            { Tab[i] = i + 1; }
            WyszLinPes();
            Console.WriteLine();
            WyszLinSre();
            Console.WriteLine();
            WyszBinPes();
            Console.WriteLine();
            WyszBinSre();
            Console.WriteLine("Done. ");
            Console.ReadKey();
        }
    }
}