c++ - 我的二进制搜索应用程序不在这里吗？

Question

所以，我正在解决这个问题: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.

我所做的是使用二进制搜索来查找天数，如下所示:

#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);
    }
}

但是，在运行我的代码时，它甚至在给定的测试用例上给出了错误的答案:

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:为了避免困惑，我没有发布库。此外，一旦获得正确的值，我会将其设置为小数点后 6 位。我只想知道，是我的逻辑不对还是我的二分查找实现不正确？

编辑:我提交的新代码

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

您正在以不合理的顺序进行测试:

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

尝试

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

我也不确定这两个递归调用。我保留了你在哪种情况下调用 which 的逻辑(因为我可能误解了你的公式)但他们向后看我。

我敢肯定的是，您应该在内部案例(然后实际上是 func(mid)-p < -eps)之前测试(并使用递归调用)两个外部案例(func(mid)-p > eps 和 abs(func(mid)-p) < eps)

编辑:该二进制搜索的更清晰(更快)版本是:

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;
    }
}

牛顿搜索可能比这更快。