gpt4 book ai didi

algorithm - 二进制搜索以找到高于给定值的最小值

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:46:02 26 4
gpt4 key购买 nike

我有一个返回 double 值的函数。下面的代码 list 是我用于测试的示例,但真正的功能将从对数据集的分析中提取。

public double f(double x)
{
return (100000 - x) / 15000;
}

可以假设较高的 x 值将始终返回较低的值,因此当 x 接近 0 时,返回的值可能会增加,但它可能始终保持在 0。

x 的值始终为正数。

当提供给定的最小值和最大值时,我希望能够找到 >= 到 7 的 f(x) 的最低值(精度只影响 0.001)。在上面的示例中,我使用 100000 作为最大值,1 作为最小值。

这是二分搜索的理想选择还是有更好的选择?

最佳答案

是也不是。

如果单调函数不收敛到有限值 - 不是,您可以使用二分查找,如下所示:

i <- 1
while (f(i) > target):
i <- i*2
binary search for target in the range `[2^(i-1),2^i]` for best candidate.

上面的复杂度是 O(log(i)) - 其中 i 是最近元素的索引。

但是请注意,如果函数收敛到某个常数值,则所有赌注都将取消。
例如,它不会帮助您为函数f(i) = 1/i 找到最接近-1 的值。在这种情况下,算法将陷入无限循环。

关于algorithm - 二进制搜索以找到高于给定值的最小值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23639936/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com