Algorithms/binarySearch.cpp at master · ugouhar/Algorithms · 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
ll binary_search(ll a[], ll n, ll key) {
    ll low = i, high = n - 1;
    while(low <= high) {
        ll mid = (low + high) / 2;
        if(a[mid] < key) {
            low = mid + 1;
        } else if(a[mid] > key) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

ll my_lower_bound(ll a[], ll n, ll key) {
    ll low = 0, high = n - 1;
    while(low <= high) {
        ll mid = (low + high) / 2;
        if(a[mid] < key) {
            low = mid + 1;
        } else if(a[mid] > key) {
            high = mid - 1;
        } else {
            high = mid - 1;
        }
    }
    return low;
}
ll my_upper_bound(ll a[], ll n, ll key) {
    ll low = 0, high = n - 1;
    while(low <= high) {
        ll mid = (low + high) / 2;
        if( a[mid] < key) {
            low = mid + 1;
        } else if(a[mid] > key) {
            high = mid - 1;
        }  else {
            low = mid + 1;
        }
    }
    return low;
}