how to calculate the time taken to search for a word using binary search

Question

int Binary_search()
{
    string word;
    cout << "Enter The Word You Want To Find : ";
    cin >> word;
    int start = 0, end = data.size() - 1;
    int mid, i = 0, counter = 0;
    while (start <= end)
    {
        mid = (end + start) / 2;
        if (data[i] == word)
            return i;

        else if (data[i] > word)
            end = mid - 1;

        else
            start = mid + 1;

        counter++;
        i++;
    }
    return -1;
}

if i wanna to know how much time this code would take to find a word in data which is a vector of type string and it loaded with words.

To measure, obtain clock times before and after, and subtract. To calculate, more information would be needed (what target system - hardware, instruction set, speed of used instructions, memory, etc). Whether calculating or measuring, the cases would need to be specified (e.g. how many words, what size words, etc etc) — Peter, Mar 30 '19 at 14:47

score 1 · Answer 1 · edited Mar 30 '19 at 14:51

1

The std::chrono::high_resolution_clock is the most accurate and hence it is used to measure execution time.

//Get the timepoint before the function is called
auto start = high_resolution_clock::now(); 
// Binary search ()
// Get ending timepoint..ie after you function is called
auto stop = high_resolution_clock::now(); 

// Get duration. Substart timepoints to  
// get durarion. To cast it to proper unit 
// use duration cast method 
auto duration = duration_cast<microseconds>(stop - start);

edited Mar 30 '19 at 14:51

πάντα ῥεῖ

1
13
116
190

answered Mar 30 '19 at 14:43

Mahendra suthar

401
5
18

can you explain it more – Muhammad bakr Mar 30 '19 at 14:46
check the updated answer – Mahendra suthar Mar 30 '19 at 14:49
which library it belongs to ? – Muhammad bakr Mar 30 '19 at 14:58
1

@Muhammadbakr It belongs to the c++ standard library (minimum standard compliance is c++11). – πάντα ῥεῖ Mar 30 '19 at 15:01
Unfortunately I am using c++98 – Muhammad bakr Mar 30 '19 at 15:04
can I find something similar to it in c++98 – Muhammad bakr Mar 30 '19 at 15:06
@Muhammadbakr "Unfortunately I am using c++98" - Then you should work to rectify that. Not seek solutions that will keep you stuck 20+ years in the past. – Jesper Juhl Mar 30 '19 at 17:35

score 1 · Answer 2 · edited Mar 30 '19 at 14:52

You can use std::chrono::high_resolution_clock for that.

// get start time
auto start = std::chrono::high_resolution_clock::now();

// do some work
Binary_search();

// get end time
auto end = std::chrono::high_resolution_clock::now();

// calculate difference as double value in seconds
std::chrono::duration<double> diff = end-start;
// print the measured value
std::cout << "Time taken : " << diff.count() << " seconds\n";

how to calculate the time taken to search for a word using binary search

2 Answers2