assign/bsearch.cpp at master · pradg73/assign · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <vector>
#include <algorithm>
//#include <random>
#include<cstdlib>
#include <ctime>
#include <chrono>
#include <random>
#include<cassert>


using namespace std;

int bs(vector<int> &v, int t)
{
    size_t N(v.size());
    size_t l(0), r(N-1);

    while (l <= r)
    {
        size_t m = l +((r-l)/2);

        cout << "l " << l << " r " << r << " m " << m << endl;
        assert(l >= 0);
        assert(r < N);
        assert( 0 <= m && m < N);

        if (v[m] == t) return m;

        if (v[m] < t )
            l = m+1;
        else
            r = m-1;
    }
    return -1;
}

int main(int argc, char*argv[])
{
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();

    std::mt19937 generator (seed);  // mt19937 is a standard mersenne_twister_engine
    //std::cout << "Random value: " << generator() << std::endl;


    vector<int> v;
    int n = 50;

    if (argc > 1)
        n = atoi(argv[1]);

    for (int i = 0; i < n;++i)
        v.push_back(generator());
    //    srand(time(NULL));

    for (const int i: v)
        cout << i << ' ';
    sort(v.begin(),v.end());

    cout << "\nsorted";
    int j = 0;
    for (const int i: v)
        cout << i << "[" << j++ << "]" << ' ';
    cout << endl;

    int t = v[generator()%n];
    if (argc > 2)
    {
        cout << "enter the number to find: ";
        cin >> t;
    }

    size_t i = bs(v,t);
    if (i == -1)
        cout << "not found\n";
    else
    {
        cout << t << " is at " << i << endl;
        cout << "check " << v[i] << endl;
        cout << "log2 " << log2(n) << endl;
    }

        cout << t << " via std bs" << binary_search(v.begin(), v.end(), t);

}