#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <set>
#include <ctime>
#include <algorithm>

int main()
{
    using namespace std;

    vector<string> vs(2000000);
    for (int i = 0; i < vs.size(); ++i)
    {
        vs[i] = to_string(i);
    }

    set<string> ss(vs.begin(), vs.end());

    {
        cout << "linear search on vector" << endl;
        time_t now = clock();
        auto s = find(vs.begin(), vs.end(), "1000000");
        cout << "linear search for \"1000000\" took: " 
        	<< double(clock() - now) / CLOCKS_PER_SEC  << " found " << *s << endl;
    }
    {
        cout << "\nbinary search on vector" << endl;
        sort(vs.begin(), vs.end());
        time_t now = clock();
        auto s = lower_bound(vs.begin(), vs.end(), "1000000");
        cout << "binary search for \"1000000\" took: " 
        	<< double(clock() - now) / CLOCKS_PER_SEC  << " found " << *s << endl;
    }
    {
        cout << "\nbinary search on set" << endl;
        time_t now = clock();
        auto s = ss.find("1000000");
        cout << "binary search for \"1000000\" took: " 
        	<< double(clock() - now) / CLOCKS_PER_SEC << " found " << *s << endl;
    }
}