Algorytmy przeszukujące

Question

Witam!

Mam do zrobienia projekt, w którym mam do zbadania dwa algorytmy przeszukujące liniowe(O(n)) i binarny O(log(n)). W zadaniu muszę zrobić tablicę sortującą rosnąco oraz zrobić do tych algorytmów punkty pomiarowe, których ma być minimum 30. Najmniejsza tablica ma mieć 2000k a największa 2^28 elementów typu int. Muszę zrealizować przypadki pesymistyczne i przypadki średnie dla wyszukiwania liniowego i wyszukiwania binarnego a dodatkowo zrobić też wersję z instrumentacją. 

Zrobiłem wyszukiwanie binarne, wyszukiwanie liniowe oraz przypadek pesymistyczny dla obydwóch tych algorytmów, ale nie rozumiem jak mam zrobić wersję z instrumentacją i jak mogę wykonać przypadek średni. Byłbym wdzięczny za ewentualne wytłumaczenie lub nakierowanie mnie co mogę zrobić. Niżej załączam linijki kodu, które dotychczas napisałem.

// Posortowanie tablicy rosnąco

public static int[] Posortowane(int rozmiar)
            {
                int[] tab = new int[rozmiar];

                for(int i = 0; i < tab.Length; i++)
                {
                    tab[i] = i;
                }
                return tab;
            }

// wyszukiwanie binarne

        public static int WyszukiwanieBinarne(int[] tab, int szukanie)
        {
            int left = 0;
            int right = tab.Length - 1;

            while(left <= right)
            {
                int CurrentPosition = left + (right - left) / 2;

                if (tab[CurrentPosition] == szukanie)
                    return CurrentPosition;
                if (tab[CurrentPosition] < szukanie)
                    left = CurrentPosition + 1;
                if (tab[CurrentPosition] > szukanie)
                    right = CurrentPosition - 1;
            }
            return -1;
        }

// wyszukiwanie liniowe

        public static int WyszukiwanieLiniowe(int[] tab, int element)
        {
            for(int i = 0; i < tab.Length; i++)
            {
                if (tab[i] == element)
                    return i;
            }
            return -1;
        }

// wyszukiwanie binarne pesymistyczne 

            int rTablicy = Convert.ToInt32(Math.Pow(2, 28)); // rozmiar tablicy
            int[] tablica = Pomocna.Posortowane(rTablicy); // tablica posortowana

            Stopwatch stoperek = new Stopwatch();
            double wynik = 0;

             for(int i = 0; i < rTablicy; i+=8000000)
            {
                stoperek.Reset();
                stoperek.Start();
                tablica = Pomocna.Posortowane(i);
                WyszukiwanieBinarne(tablica, -1);
                stoperek.Stop();
                wynik = stoperek.ElapsedTicks;
                Console.WriteLine($"{wynik};{i}");

            } 

// wyszukiwanie liniowe pesymistyczne 

            int rTablicy = Convert.ToInt32(Math.Pow(2, 28)); // rozmiar tablicy
            int[] tablica = Pomocna.Posortowane(rTablicy); // tablica posortowana

 for(int i = 0; i < rTablicy; i+=8000000 ) // wyszukiwanie liniowe pesymistyczne
            {
                tablica = Pomocna.Posortowane(i);
                stoperek.Reset();
                stoperek.Start();
                WyszukiwanieLiniowe(tablica, -1);
                stoperek.Stop();
                wynik = stoperek.ElapsedMilliseconds;
                Console.WriteLine($"{wynik};{i}");
            }