Спринт 6. Не худший случай.

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

using namespace std;

int EffectiveCount(const vector<int>& v, int n, int i) {
    if (size(v)*(i + 1)/(n + 1) > log2(size(v))){
        cout << "Using upper_bound"s << endl;
        return upper_bound(begin(v), end(v), i) - begin(v);
    } else {
        cout << "Using find_if"s << endl;
        return find_if(begin(v), end(v), [i](int var){return i < var;}) - begin(v);
    }
    return 0;
}

int main() {
    static const int NUMBERS = 1000000;
    static const int MAX = 1000000;

    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;
}