Algorytm szukania liczby - błędny czas

Witam, mam znaleźć w tablicy liczbę oraz podać czas jej wyszukiwania na 2 sposoby: liniowo (szukam od 1 elementu aż do znalezienia) oraz binarnie(dziele tablice na pół i porównuję z szukaną liczba, odrzucam połowe itd.). Ogólnie chodzi o porównanie czasu przeszukiwania tablicy dla coraz większego rozmiaru. Szukanie liniowe działa mi bezproblemowo, czas rośnie proporcjonalnie do wielkości tablicy, mam jednak problem z szukaniem binarnym. Czas powinien rosnąć logarytmicznie, tymczasem u mnie np. dla mniejszej tablicy czas wynosi więcej niż dla większej tablicy. Tak wygląda funkcja szukająca:

int SzukajBinarnie(int *tab, int rozmiar, int s)
{                                                
    int l=0,pom;                                
    int p=rozmiar-1;
    fstream plik;

    StartCounter();
    while(true)
    {
        if(l>p)
        {
            cout<<"Wyszukiwanie binarne: nie znalazlem"<<endl;
            break;
        }

        pom=(l+p)/2;

        if(tab[pom]==s)
        {
            cout<<"Znalazlem binarnie, nr indeksu: "<<pom<<endl;
            break;
        }

        else if (tab[pom]<s)
            l=pom+1;
        else
            p=pom-1;
    }

    plik.open("binarnie.txt", ios::out|ios::app);
    plik<<rozmiar<<"\t"<<GetCounter()<<endl;
    plik.close();
    return 0;
}

Gdzie mam błąd?

Po pierwsze nie powinieneś brać pod uwagę otwierania pliku...
Po drugie to będziesz obserwował tylko dla dużych zakresów danych, powiedzmy kilku MB minimum.
Po trzecie czemu nie użyłeś std::binary_search?

Ok, wyrzuciłem odczytanie czasu zanim otworzę plik. Nie wiedziałem o binary_search, ale to nie powinno mieć znaczenia.
Coś musi być źle, skoro zaczynam od tablicy o rozmiarze 1000, kończe na 64mln a różnica między czasami jest znikoma, nie mówiąc już, że nie rośnie w górę tylko się waha.
Może wrzucić cały program, być może problem występuje w innym miejscu?

A ile prób robisz? Bo wiesz że przecież dla różnych liczb to szukanie może trwać krócej - log(n) to jest górne ograniczenie tylko. No i próby na 1000 elementów są bez sensu bo wszystko i tak łyknie cache procesora i czas wykonywania będzie znikomy. Dopiero jak masz powyżej kilku MB to może to mieć sens.

Przykładowy wynik działania programu, po lewej rozmiar tablicy, po prawej czas - dla każdego rozmiaru szukam 10 razy i z tego wyliczam średnią.

//mała pomyłka, ostatni rozmiar to nie 900100 tylko 19683000, a średnia 1,64211 - źle mi się skopiowało.

Wyszukuje dla opcji pesymistycznej, czyli szukanej liczby nie ma w tablicy - dzięki temu przeszukuję ją całą. (wypełniam tablice jedynkami, a szukana liczba to 0).

Z tej twojej średniej odrzucałbym skrajne wyniki bo zapewne wynikają z tego że komputer chwilowo robił coś innego, I/O jakieś albo coś. Bo widzisz chyba że na przykład dla 729000 masz wyniki po 1,2sek a jeden 26? ;]