CODEWITHSUNDEEP
c++
Arun Kumar
Arun Kumar

Reputation: 63

Calculating Running Time of Binary Search

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;   
}

Upvotes: 2

Views: 1627

Answers (5)

Semyon Burov
Semyon Burov

Reputation: 1172

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.

Upvotes: 0

Some programmer dude
Some programmer dude

Reputation: 409136

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.

Upvotes: 1

pureofpure
pureofpure

Reputation: 1090

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!

Upvotes: 0

ALEXANDER KONSTANTINOV
ALEXANDER KONSTANTINOV

Reputation: 913

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++.

Upvotes: 0

Sunz
Sunz

Reputation: 64

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.

Upvotes: 0

Related Questions