600B | Codeforces | Queries about less or equal elements

Question

Here's the question: Link

My code is below:

#include <bits/stdc++.h>

using namespace std;
#define output(x) cout << x << endl
#define ll long long

ll binarySearch(vector<ll> vec, ll num, ll n) {
    ll left = 0;
    ll right = n-1;
    ll mid = 0;

    while (left <= right) {
        mid = (left+right)/2;

        if (left == right) {
            break;
        }

        if (vec[mid] <= num) {
            left = mid+1;
        }
        else {
            right = mid;
        }
    }

    if (vec[mid] <= num) {
        return mid+1;
    }

    return mid;
}

int main(int argc, char const *argv[])
{ 
    ios_base::sync_with_stdio(false);
    ll a, b;
    cin >> a >> b;
    vector<ll> avec(a);

    for (auto &it: avec) {
        cin >> it;
    }

    sort(avec.begin(), avec.end());

    ll curr;
    map<ll, ll> answers;

    while (b--) {
        cin >> curr;

        if (answers[curr] != 0) {
            cout << answers[curr] << " ";
        }
        else {
            ll ans = binarySearch(avec, curr, a);
            answers[curr] = ans;

            cout << ans << " "; 
        }

    }

    cout << "\n";
    return 0;
}

This doesn't pass the time limits. However, when I use the internal function upper_bound instead of calling my binarySearch, it passes upper_bound is called as below

cout << (upper_bound(avec.begin(), avec.end(), curr) - avec.begin()) << " ";

Is there a way to submit this question successfully without needing to use internal function? Can the binary search be more optimised?

Answer 1

Here, ll binarySearch(vector<ll> vec, ll num, ll n) {, you pass the vector vecby copy.

The complexity of the copy is O(n). So, even if the algorithm is O(logn), the global complexity of the function is still O(n).

By making the call by reference:

ll binarySearch(vector<ll> &vec, ll num, ll n) {

The call by itself costs O(1) and the global complexity of the function remains O(logn).