Binary Search

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Returns the first index i such that a[i] >= x; if not found, returns n
5
int lower_bound_index(const vector<int>& a, int x) {
6
    int n = (int)a.size();
7
    int L = 0, R = n; // search in [L, R)
8
    while (L < R) {
9
        int mid = L + (R - L) / 2; // overflow-safe
10
        if (a[mid] >= x) {
11
            R = mid; // keep mid; answer is in [L, mid]
12
        } else {
13
            L = mid + 1; // answer is in (mid, R)
14
        }
15
    }
16
    return L; // L == R: first >= x or n if none
17
}
18
19
// Returns the first index i such that a[i] > x; if not found, returns n
20
int upper_bound_index(const vector<int>& a, int x) {
21
    int n = (int)a.size();
22
    int L = 0, R = n; // search in [L, R)
23
    while (L < R) {
24
        int mid = L + (R - L) / 2;
25
        if (a[mid] > x) {
26
            R = mid; // shrink right; mid could be the first > x
27
        } else {
28
            L = mid + 1; // need strictly larger, go right
29
        }
30
    }
31
    return L;
32
}
33
34
int main() {
35
    ios::sync_with_stdio(false);
36
    cin.tie(nullptr);
37
38
    vector<int> a = {1, 2, 2, 2, 4, 5};
39
    for (int x : {0, 2, 3, 6}) {
40
        int lb = lower_bound_index(a, x);
41
        int ub = upper_bound_index(a, x);
42
        int cnt = ub - lb;
43
        cout << "x=" << x
44
             << " lb=" << lb
45
             << " ub=" << ub
46
             << " count=" << cnt << "\n";
47
    }
48
    return 0;
49
}
50

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Returns floor(sqrt(n)) for n >= 0 using binary search on answer.
5
// Predicate: p(x) = (x*x <= n), which is nondecreasing in x until boundary.
6
long long isqrt_floor(long long n) {
7
    long long L = 0, R = min(n, (long long)2e9); // search [L, R]
8
    long long ans = 0;
9
    while (L <= R) { // closed interval
10
        long long mid = L + (R - L) / 2;
11
        // Avoid overflow: mid*mid <= n  <=> mid <= n / mid (if mid > 0)
12
        bool ok = (mid == 0) ? true : (mid <= n / mid);
13
        if (ok) {
14
            ans = mid;       // mid is feasible, try to go higher
15
            L = mid + 1;
16
        } else {
17
            R = mid - 1;     // infeasible, go lower
18
        }
19
    }
20
    return ans;
21
}
22
23
int main() {
24
    ios::sync_with_stdio(false);
25
    cin.tie(nullptr);
26
27
    vector<long long> tests = {0, 1, 2, 3, 4, 8, 9, 10, (long long)1e12};
28
    for (auto n : tests) {
29
        cout << "n=" << n << " floor_sqrt=" << isqrt_floor(n) << "\n";
30
    }
31
    return 0;
32
}
33

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given stall positions and k cows, place cows to maximize the minimum distance between any two.
5
// We binary search the answer d and check feasibility greedily.
6
7
bool canPlace(const vector<int>& pos, int k, int d) {
8
    int count = 1; // place first cow at pos[0]
9
    int last = pos[0];
10
    for (size_t i = 1; i < pos.size(); ++i) {
11
        if (pos[i] - last >= d) {
12
            ++count;
13
            last = pos[i];
14
            if (count >= k) return true; // early exit
15
        }
16
    }
17
    return false;
18
}
19
20
int maximizeMinDistance(vector<int> pos, int k) {
21
    sort(pos.begin(), pos.end());
22
    int n = (int)pos.size();
23
    int L = 0;                         // always feasible (distance 0)
24
    int R = pos.back() - pos.front();  // maximum possible distance
25
    int best = 0;
26
    while (L <= R) { // closed interval for max-feasible
27
        int mid = L + (R - L) / 2; // candidate minimum distance
28
        if (canPlace(pos, k, mid)) {
29
            best = mid;     // feasible; try larger distance
30
            L = mid + 1;
31
        } else {
32
            R = mid - 1;    // infeasible; try smaller distance
33
        }
34
    }
35
    return best;
36
}
37
38
int main() {
39
    ios::sync_with_stdio(false);
40
    cin.tie(nullptr);
41
42
    vector<int> stalls = {1, 2, 8, 12, 17};
43
    int k = 3;
44
    cout << "max min distance = " << maximizeMinDistance(stalls, k) << "\n"; // Expected 6 (1,8,17)
45
    return 0;
46
}
47

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given rope lengths, find the maximum piece length L so that we can cut at least k pieces.
5
// Real-valued binary search with tolerance epsilon.
6
7
double maxPieceLength(const vector<double>& a, long long k, double eps = 1e-7) {
8
    double L = 0.0, R = 0.0;
9
    for (double x : a) R = max(R, x);
10
    // Invariant: answer in [L, R]
11
    for (int it = 0; it < 200 && R - L > eps; ++it) { // fixed iterations + epsilon guard
12
        double mid = (L + R) / 2.0;
13
        if (mid == 0.0) { L = mid; continue; }
14
        long long pieces = 0;
15
        for (double x : a) pieces += (long long)(x / mid);
16
        if (pieces >= k) {
17
            L = mid; // feasible: we can try longer pieces
18
        } else {
19
            R = mid; // infeasible: need shorter pieces
20
        }
21
    }
22
    return L; // within eps of the true optimum
23
}
24
25
int main() {
26
    ios::sync_with_stdio(false);
27
    cin.tie(nullptr);
28
29
    vector<double> ropes = {4.0, 7.5, 9.2};
30
    long long k = 7;
31
    cout.setf(std::ios::fixed); cout << setprecision(6);
32
    cout << "max piece length ≈ " << maxPieceLength(ropes, k) << "\n";
33
    return 0;
34
}
35