Lower-Bound algorithm getting Time Limit Exceeded

Question

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll lower_bound(vector<ll> arr, ll tar, ll n)
{
    ll l = 0, h = n - 1;
    ll ans = n;
    while (l <= h)
    {
        ll mid = l + (h - l) / 2;
        if (arr[mid] >= tar)
        {
            ans = mid;
            h = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;
    vector<ll> arr(n, 0);
    for (ll i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    ll q;
    cin >> q;
    while (q--)
    {
        ll val;
        cin >> val;
        ll ans = lower_bound(arr, val, n);
        // cout << ans << endl;
        if (ans == n)
        {
            cout << "No " << n << endl;
        }
        else if (arr[ans] == val)
        {
            cout << "Yes " << ans + 1 << endl;
        }
        else if (arr[ans] != val)
        {
            cout << "No " << ans + 1 << endl;
        }
    }

    return 0;
}

I have implemented the Lower Bound algorithm without using the standard library. But Why I am getting time limit exceeded for the above code?

Is the STL's std::lower_bound() faster than the above code?

The above code is \$O(n \log n)\$.

Problem Link: https://www.hackerrank.com/challenges/cpp-lower-bound/leaderboard

Answer 1

#include <bits/stdc++.h>

That's not a standard header. It's an implementation detail of your compiler, and as such is not a reliable include from version to version, never mind for users of other compilers.

The correct headers here are

#include <iostream>
#include <vector>

---

using namespace std;

This is a poor (and potentially dangerous) practice. The name std is intentionally very short, so shouldn't be too much trouble to type.

---

typedef long long ll;

Why are we obfuscating the code like this? If we want an alias for this type, why give it such an unreadable name?

---

ll lower_bound(std::vector<ll> arr, ll tar, ll n)

This is nothing like the signature of std::lower_bound. Even considering the version that doesn't take a comparator, the standard library version is much more flexible, accepting any matched pair of iterators, and returning an iterator.

I can guess what arr is, but tar and n are mysterious, and there's not even a comment to help. I had to spend some time digging into the implementation to discover that tar is the value we're searching for, and n seems to be a signed version of arr.size().

---

ll l = 0, h = n - 1;

One line per declaration, please. Declaring multiple variables (even worse - 1-char variables) is harder to read.

It appears that you're using an inclusive range for search. You'll find that half-open ranges are easier to work with.

---

   ll mid = l + (h - l) / 2;

Well done for avoiding the common overflow bug here. Though I'd normally use std::midpoint() to get the same result more clearly.

---

std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);

sync_with_stdio(false) unties std::cin, so the second statement is redundant. And since we never use stdio, there's nothing to be gained from untying it anyway.

---

ll n;
std::cin >> n;

Never ignore input errors - we need to be checking whether std::cin is good() before we use n. This isn't just a one-off; the whole code is fragile this way.

---

    std::cout << "No " << n << std::endl;

Why are we flushing output after every line, with std::endl? Is there a reason not to simply write an ordinary newline ('\n')? If the writer won't produce our next input until it receives this output, then use a comment to say so.

---

return 0;

Not necessary from main() - reaching the end of function has the same effect.

Answer 2

Some style points

The code is marked C++ so use using not typedef, and instead of long long I think you should be specific in your architecture type int64_t, this is about int vs int32_t but the points apply I'm not sure if there'll be a speed implication, but you could check out godbolt.org and check the assembly output and make sure they're the same etc

(I checked, godbolt.org, there's no difference between)

using ll=long long

and

int64_t

It produces the same assembler output thus no effect on performance, so you can use the more 'modern' syntax without performance penalty)

Variables could have more descriptive names and don't use using namespace std . I know it's a short piece of code, but it's a good habit to get out of. Your IDE or TextEditor can be 'taught' to prepend std:: to cin , cout etc. and thus it doesn't take any more keystrokes to type.

Maybe a comment or two here and there explaining why you did certain things, helps (especially in the light of frugal variable names) when you come back to look at your code after a year or two away.

The code is nicely formatted, however if you're going to have some user interaction is it worth having a bit more than "No" or "Yes" ?

The comments have addressed your question, these are some extra bits.