Calculating Running Time of Binary Search

Question

The following Binary Search program is returning a running time of 0 milliseconds using GetTickCount() no matter how big the search item is set in the given list of values.

Is there any other way to get the running time for comparison?

Here's the code :

#include <iostream>
#include <windows.h>
using namespace std;

int main(int argc, char **argv)
{
        long int i = 1, max = 10000000;
        long int *data = new long int[max];
        long int initial = 1;
        long int final = max, mid, loc = -5;
        for(i = 1; i<=max; i++)
        {
            data[i] = i;
        }

        int range = final - initial + 1;
        long int search_item = 8800000;

        cout<<"Search Item :- "<<search_item<<"\n";

        cout<<"-------------------Binary Search-------------------\n";
        long int start = GetTickCount();
        cout<<"Start Time : "<<start<<"\n";

        while(initial<=final)
        {
            mid=(initial+final)/2;

            if(data[mid]==search_item)
            {
                loc=mid;
                break;
            }

            if(search_item<data[mid])
                final=mid-1;

            if(search_item>data[mid])
                initial=mid+1;
        }
        long int end = GetTickCount();
        cout<<"End Time : "<<end<<"\n";
        cout << "time: " << double(end - start)<<" milliseconds \n";
        if(loc==-5)
            cout<<" Required number not found "<<endl;
        else
            cout<<" Required number is found at index "<<loc<<endl;
        return 0;   
}

You don't need a loop to fill in `data` or set `final`. The value of `final` can be easily calculated, and to initialize `data` you could use [`std::iota`](http://en.cppreference.com/w/cpp/algorithm/iota). — Some programmer dude, Jan 24 '16 at 20:11
As for your problem, I recommend you count your curly-braces and check your indentation. Or remove that `return` statement (and rely on the implicit compiler-generated return statement) and run again to see what happens. Or simply step through the code in a debugger (which should have been your first instinct). — Some programmer dude, Jan 24 '16 at 20:12
it is better to use DWORD as GetTickCount documentation mentioned — Pooya, Jan 24 '16 at 20:17
Edited Code to reflect final without loop but in case of using std::iota, I'm getting error 'iota' is not a member of 'std' — Arun Kumar, Jan 24 '16 at 20:31

score 1 · Answer 1 · answered Jan 24 '16 at 20:21

Your code looks like this:

int main()
{
    // Some code...

    while (some_condition)
    {
        // Some more code...
        // Print timing result
        return 0;
    }
}

That's why your code prints zero time, you only do one iteration of the loop then you exit the program.

score 0 · Answer 2 · answered Jan 24 '16 at 20:11

0

Try to use the clock_t object from the time.h header:

clock_t START, END;
        START = clock();
        **YOUR CODE GOES HERE**
        END = clock();
        float clocks = END - START;
        cout <<"running time : **" << clocks/CLOCKS_PER_SEC << "** seconds" << endl;

CLOCKS_PER_SEC is a defined var to convert from clock ticks to seconds.

answered Jan 24 '16 at 20:11

Sunz

64
1
1
7

Used your approach but I'm still getting 0 seconds. – Arun Kumar Jan 24 '16 at 20:44
Write the code here below after you added the clock_t object, it may support us to help you. @ArunKumar – Sunz Jan 24 '16 at 20:54

score 0 · Answer 3 · edited May 23 '17 at 10:27

0

https://msdn.microsoft.com/en-us/library/windows/desktop/ms724408(v=vs.85).aspx This article says that result of GetTickCount will wrap to zero if you system runs for 49.7 days.

You can find here: Easily measure elapsed time how to measure time in C++.

edited May 23 '17 at 10:27

Community

1
1

answered Jan 24 '16 at 20:11

ALEXANDER KONSTANTINOV

913
1
7
21

score 0 · Answer 4 · answered Jan 24 '16 at 20:12

0

You can use time.h header

and do something like this in your code :

clock_t Start, Stop;
double sec;

Start = clock();
//call your BS function
Stop = clock();

Sec = ((double) (Stop - Start) / CLOCKS_PER_SEC);

and print the sec!

I hope this helps you!

answered Jan 24 '16 at 20:12

pureofpure

1,060
2
12
31

Used your approach but I'm still getting 0 seconds. – Arun Kumar Jan 24 '16 at 20:44

Semyon Burov · Answer 5 · 2016-01-24T22:15:05.290

The complexity of binary search is log2(N), it's about 23 for N = 10000000. I think its not enough to mesure in realtime scale and even clock. In this case you should use unsigned long long __rdtsc(), that returns number of processor ticks from last reset. Put this before and after your binary search and place cout << start; after obtaining end time. Overwise time of output would be included.

There is also memory corruption around data array. Index in C runs from 0 to size - 1, so thereis no data[max] element.

And delete [] data; before calling return.

Calculating Running Time of Binary Search

5 Answers5