CODEWITHSUNDEEP
c++binary-search
xennygrimmato
xennygrimmato

Reputation: 2796

Binary search to upper bound for a real number function

Given an integer X, I need to find the maximum integer N such that N*log(N) <= X.

I am using binary search to compute the answer, but I think the loop is running infinitely for some cases.

This is my binary search function:

int f(int X)
{
    int lo=1, hi=time;
    while(lo < hi)
    {
        int mid = lo + hi;
        mid/=2;
        if(mid*log2((double)mid) == X)
        {
            return mid;
        }
        if(mid*log2((double)mid) <= X)
        {
            hi = mid;
        }
        else lo=mid;
    }
    return lo;
}

Is my approach correct? If yes, what is the bug in my code? If no, what is the correct approach?

Upvotes: 1

Views: 94

Answers (1)

NPE
NPE

Reputation: 500317

Consider what happens if hi - lo == 1. In this case mid equals lo, so lo = mid is a no-op and you can end up in an infinite loop.

Upvotes: 1

Related Questions