Getting TLE using Binary Search in TRIPLETMIN

help
1

I was solving the problem and came up with the logic, and applied binary search, but still got TLE.
Now I looked up the solution and found that they came up with the same logic, just that they applied lower_bound to find the index.
Here’s is my code :

#include <bits/stdc++.h>
using namespace std;
#define int long long int

int binSearch(int k, vector<int> smaller)
{
    int n = smaller.size();
    int lo = 0, hi = n, mid;

    while (lo < hi)
    {
        mid = lo + (hi - lo) / 2;
        if (k <= smaller[mid])
        {
            hi = mid;
        }
        else
        {
            lo = mid + 1;
        }
    }
    return hi;
}

int32_t main()
{

    int t;
    cin >> t;
    while (t--)
    {

        int n, q;
        cin >> n >> q;
        vector<int> a(n);
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        sort(a.begin(), a.end());

        vector<int> smaller(n);
        for (int i = 0; i < n; i++)
        {
            int l = n - i - 1;
            if (l > 1)
            {
                smaller[i] = l * (l - 1) / 2;
                if (i > 0)
                    smaller[i] += smaller[i - 1];
            }
            else
            {
                smaller[i] = smaller[i - 1];
            }
        }

        for (int i = 0; i < q; i++)
        {
            int k;
            cin >> k;
            int index = binSearch(k, smaller);
            cout << a[index] << endl;
        }
    }

    return 0;
}

Now, time complexity for binary search, as well as lower_bound, is O(logn). Then why am I getting TLE using Binary Search??
Do suggest some correction in my binSearch function.

2

@yoder2k4
I have corrected your code a bit to remove tle . U r getting it because of using vector instead of array.
include <bits/stdc++.h>
using namespace std;
define ll int

ll binSearch(long long int k, long long int smaller [],long long int n)
{

long long int lo = 0, hi = n-1, mid;
long long int ans=0;
while (lo <= hi)
{
    mid = lo + (hi - lo) / 2;
    if (k <= smaller[mid])
    {
        ans=mid;
        hi = mid-1;
    }
    else
    {
        lo = mid + 1;
    }
}
return ans;

}

int main()
{

ll t;
cin >> t;
while (t--)
{

    long long  int n, q;
    cin >> n >> q;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a+n);

    long long int smaller[n-2];
    for (ll i = 0; i < n-2; i++)
    {
        long long int  l = n - i - 1;
            smaller[i] = (l * (l - 1)) / 2;
            if (i > 0)
                smaller[i] += smaller[i - 1];
    }

    for (int i = 0; i < q; i++)
    {
        long long int  k;
        cin >> k;
        ll index = binSearch(k, smaller,n-2);
        cout << a[index] << endl;
    }
}

return 0;

}

1 Like