Is my application of binary search not right here?

Question

So, I was solving this problem: http://www.spoj.com/problems/IMMERSED/

A fantastic discovery is about to happen in the biology field, and you are part of the team making the research. The research is about measuring the cells growth in an environment oxygenless and in presence of a toxic substance. The team came to a courious hypothesis, the analyzed data tells them that: the growth, the number of days and the toxicity; are related by this formula:

P = N*N^cN;

where P is the growth measured in thousands of cells.

N is the elapsed number of days.

and c is the constant that relates to the toxicity level of the experiment.

Your biology partners need to takeout some tissues from the cells when these cells reach a specific growth. They require you to write a program that tells them the exact time when this will happen, given a toxicity level and the growth required.

Input

The first line is T (1 ≤ T ≤ 40,000), the number of test cases, then T test cases follow.

Each test case is a line with 2 integers(P c) separated by a space.

P (1 ≤ P ≤ 10¹⁵)

c (1 ≤ c ≤ 5)

Output

For each test case you have to output the expected time in decimal format.

What I did was used binary search for finding the number of days as follows:

#define eps 1e-7
const double cont = 14.0;
double p,c;
double binary (double start, double end);
double func (double n);
int main (void)
{
    int t;
    cin>>t;
    while (t != 0)
    {
        cin>>p>>c;
        double mid,ans,start=0,end=cont;
        ans = binary(start,end);
        cout.precision(6);
        cout<<fixed<<ans<<"\n";         
        t--;
    }
    return 0;
}

double func (double n)
{
    double ret = n*pow(n,c*n);
    return ret;
}

double binary (double start, double end)
{
    if (start <= end)
    {
        double mid = start + (end-start)/2.0;
        if (func(mid)-p <= eps)
            return mid;
        else if (func(mid)-p > eps)
            return binary(start,mid);
        else
            return binary(mid,end);
    }
}

However, on running my code, it gives incorrect answer on even the given test cases which are:

Input:
3
1 1
3 4
100 1
Output:
1.000000
1.207384
3.086308

My output (for the above input)

0.875
0.875
1.75

PS: I didn't post the libraries and all to avoid cluttering. Also, I will set it to be 6 decimal places once I get the correct value. I just want to know, is my logic incorrect or my binary search has been implemented incorrectly?

Edit: New code I submitted

double binary (double start, double end)
    {
        if (start <= end)
        {
            double mid = start + (end-start)/2.0;
            double delta = func(mid) - p;
            if (delta < -1*eps)
                return binary(mid,end);
            else if (delta > eps)
                return binary(start,mid);
            else
                return mid;
        }
    }

Answer 1

You are testing in an unsound sequence:

if (func(mid)-p <= eps)
    return mid;
else if (func(mid)-p > eps)
    return binary(start,mid);
else
    return binary(mid,end);

Try

if (func(mid)-p < -eps)
    return binary(mid,end);
else if (func(mid)-p > eps)
    return binary(start,mid);
else
    return mid;

I'm also not sure of the two recursive calls. I kept your logic for which is called in which case (because I might have misunderstood your formula) but they look backwards to me.

What I'm sure of is that you should test for (and use a recursive calls for) the two outside cases (func(mid)-p < -eps and func(mid)-p > eps) before the inside case (which is then effectively abs(func(mid)-p) < eps)

Edit: The cleaner (faster) version of that binary search is:

double binary (double start, double end)
{
    for (;;)
    {
        double mid = (start + end) * .5;
        double delta=func(mid)-p;

        if ( delta < -eps)
            start = mid;
        else if (delta > eps)
            end = mid;
        else
            return mid;
    }
}

A Newton search is likely faster than that.

Answer 2

Beside the problem with the search JSF explained, you're also calculating way more accurately than you need to.

You need N with an accuracy of 10^-6. With your implementation, you're searching until you find the value where you have P with an accuracy of 10^-7. Since the function is exponential and therefore very steep, i.e. P changes very quickly with N, that's going to result in much more computation than necessary.

Instead, you should have a stopping condition end - start < 1e-6.

Now here I have a semantic issue: Does an accuracy of 10^-6 mean that all the digits have to be correct, or is the last one allowed to be off by 1? If it's allowed, either start or end will be a good answer after stopping. If not, you could round them upwards to the nearest 10^-6. You should round up because the statement is probably asking for the first N where func(N) > P, not an approximation for equality. Then if those are different, check if the rounded value of start satisfies the statement. If yes, output that, if not, output the rounded value of end.

Given the upper bound of 14.0, the search space is just 14.0 / 1e-6 = 1.4 * 10^8 elements. The base 2 log of that is just over 27, so you should only need 28 iterations for each test case (maybe 27 if you calculate a more accurate upper bound). This definitely shouldn't require complicated optimizations to pass.