二进制搜索以查找未知数字

本文关键字：未知数 数字 未知 查找 搜索 二进制 | 更新日期: 2024-10-19 22:02:43

我有一个名为Slice的函数。它消耗2个值。第一节点值和第二节点值。我试图找到[First，Second]之间的值，包括使函数G（x）为零或非常接近，最接近小数点后2位的值。我可以使用从第一个数字开始并递增.01的迭代函数来解决这个问题，但这可能需要很长时间。

我试着用二进制运行时来实现它。棘手的是，我不知道找到中点后该切哪一片。如果我能得到一些提示或建议，请继续。

public double Slice(decimal first, decimal last)
{
    double firstNodeValue         = FinalOptionDecider(first);        
    double midNodeValue           = FinalOptionDecider((last + first) / 2);
    double lastNodeValue          = FinalOptionDecider(last);   
}

二进制搜索以查找未知数字

二进制搜索依赖于排序的数据来决定下一步搜索哪一半。因此，除非要传递数据的函数也按排序顺序保留数据，否则不能使用二进制搜索。

你有两个选择：

  • 放弃二进制搜索，只做线性搜索
  • 处理所有输入，对输出进行排序和二进制搜索（您可以在字典中将输入和输出配对以检索输入）

作为任意函数的一般问题，这可能很难解决。如果你能做出某些假设，这会变得容易得多。你已经开始使用的算法叫做平分算法。

首先，你需要将你想要的价值括起来。因此，如果您希望FinalOptionDecider(x)返回零，那么您的firstNodeValue和lastNodeValue必须是正的和负的。如果它们都是正的或都是负的，那么您无法将所需的值括起来，并且您无法保证在first和last之间搜索会找到答案。你也不能保证你能做出下一段中描述的决定。所以先检查一下。

这个条件基本上就是你的答案。。。当你得到midNodeValue时，你需要检查你想要的值是在firstNodeValue和midNodeValue之间，还是在midNodeValue和lastNodeValue之间。根据它是哪一个，您需要再次在该间隔上进行切片。重复此步骤，直到达到所需的精度。

如果你的函数有多个零（就像g（x）=x^2-1一样），那么你只能找到其中一个零。

您只是在寻找一个根查找算法。您在这里开始实现的只是"二分法"。二等分不是最快的，但它的主要优点是，只要函数在区间上改变符号，并且函数是连续的，它就可以简单地保证在指定区间内收敛到根（因此，根据中值定理，根保证存在于区间中）

public static decimal FindRoot( decimal first, decimal last, Func<decimal, double> f, double value, decimal tolerance = 0.01m )
{
    double fa = f( first );
    double fb = f( last );
    if( fa * fb > 0 )
    {
        throw new ArgumentException( "Interval not guaranteed to contain root." );
    }
    else if( fa == 0 )
    {
        return first;
    }
    else if( fb == 0 )
    {
        return last;
    }
    while( Math.Abs( first - last ) > tolerance )
    {
        decimal mid = ( first + last ) / 2;
        double fc = f( mid );
        if( fc * fb < 0 )
        {
            first = mid;
            fa = fc;
        }
        else if( fc * fa < 0 )
        {
            last = mid;
            fb = fc;
        }
        else
        {
            return mid;
        }
    }
    return ( first - last ) * (decimal) ( fa / ( fb - fa ) ) + first;
}

二进制搜索就是缩小一个区间，直到这个区间只包含一个值。我不知道你说的随机是什么意思，但二进制排序只能在排序的数据集上执行请记住，随机搜索几乎总是比排序然后搜索更快

相关文章：