# Getting TLE using Binary Search in TRIPLETMIN

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.

@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