СПРИНТ № 6 | Просто о сложности. Теория быстродействия | Урок 10: Не худший случай

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>
#include <cmath>

using namespace std;

int EffectiveCount(const std::vector<int>& v, int n, int i) {
    if (log2(v.size()) > static_cast<int64_t>(v.size()) * (i + 1) / (n + 1)) {
        auto beg_find = std::find_if(v.begin(), v.end(), [&i](int x) {
            return x > i;
            });
        cout << "Using find_if" << endl;
        return (beg_find - v.begin());
    }
    else {
        auto beg_upper = std::upper_bound(v.begin(), v.end(), i);
        cout << "Using upper_bound" << endl;
        return (beg_upper - v.begin());
    }
}

int main() {
    static const int NUMBERS = 1'000'000;
    static const int MAX = 1'000'000'000;

    mt19937 r;
    uniform_int_distribution<int> uniform_dist(0, MAX);

    vector<int> nums;
    for (int i = 0; i < NUMBERS; ++i) {
        int random_number = uniform_dist(r);
        nums.push_back(random_number);
    }
    sort(nums.begin(), nums.end());

    int i;
    cin >> i;
    int result = EffectiveCount(nums, MAX, i);
    cout << "Total numbers before "s << i << ": "s << result << endl;
}