Cp---dsa/41.cpp at master · Pushpendra100/Cp---dsa · 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
86
#include <bits/stdc++.h>
using namespace std;
// Implement Upper Bound & Lower Bound with Binary Search


int lower_bound(vector<int> &v, int element){
    int lo = 0, hi = v.size() -1;
    int mid;
    while (hi-lo>1)
    {
        int mid = (hi+lo)/2;
        if(v[mid]< element){
            lo = mid+1;
        }else{
            hi = mid;
        }
    }
    if(v[lo]>=element){
        return lo;
    }
    if(v[hi]>= element){
        return hi;
    }
    return -1;

}

int upper_bound(vector<int> &v, int element){
    int lo = 0, hi = v.size() -1;
    int mid;
    while (hi-lo>1)
    {
        int mid = (hi+lo)/2;
        if(v[mid]<= element){
            lo = mid+1;
        }else{
            hi = mid;
        }
    }
    if(v[lo]>element){
        return lo;
    }
    if(v[hi]> element){
        return hi;
    }
    return -1;

}


int main() {

    /*
    input
    6
    2 4 8 12 17 26
    18
    */

    int n;
    cin>>n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        cin>>v[i];
    }
    sort(v.begin(), v.end());
    int element;
    cin>>element;
    int lb = lower_bound(v,element);
    int ub = upper_bound(v,element);
    cout<<lb<<" "<<(lb!=-1?v[lb]:-1)<<endl;
    cout<<ub<<" "<<(ub!=-1?v[ub]:-1)<<endl;

    // similarly we can also pass the starting iterator as well as ending iterator in the lower and upper bound function


    return 0;
}