我需要在不运行 O(n) 的情况下找到给定范围内的最小值。
数组可能是一些对角线或双曲线。这是三个示例数组:
var arrDiag1 = new double[10] { 0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4, 4.5 };
var arrDiag2 = new double[10] { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
var arrHyperbole = new double[10] { 9, 8, 7, 6, 5, 4, 3, 4, 5, 6 };
我尝试根据沙漠练习中的直线进行某种计算,但结果并不理想。 谁有更好的主意?
感谢帮助
更新
在 dasblinkenlight 的帮助下,我设法找到了这个方法:
private double BinarySearchMin(double[] arr, int left, int leftMiddle, int rightMiddle, int right)
{
if (left == right)
return arr[left];
if (arr[leftMiddle] < arr[rightMiddle])
{
right = rightMiddle;
leftMiddle = ((right - left) / 3);
rightMiddle = ((right - left) / 3 * 2);
return BinarySearchMin(arr, left, leftMiddle, rightMiddle, right);
}
if (arr[leftMiddle] > arr[rightMiddle])
{
left = leftMiddle;
leftMiddle = ((right - left) / 3) + left;
rightMiddle = ((right - left) / 3 * 2) + left;
return BinarySearchMin(arr, left, leftMiddle, rightMiddle, right);
}
if (arr[leftMiddle] == arr[rightMiddle])
{
left = leftMiddle;
right = rightMiddle;
leftMiddle = ((right - left) / 3) + left;
rightMiddle = ((right - left) / 3 * 2) + left;
return BinarySearchMin(arr, left, leftMiddle, rightMiddle, right);
}
return -1;
}
在第一个数组中有效,但在第二个和第三个数组中无效。 我在这里缺少什么?
最佳答案
如果函数只有一个最小值,使用Ternary Search :
ternary search algorithm is a technique for finding the minimum or maximum of a unimodal function.
想法是将范围分成三个相等的部分,探测两个搜索点,然后“拉入”不包含最小值的那个。假设搜索点 i1
位于区间左侧,i2
位于区间右侧:
- 如果f[i1] < f[i2],则最小值在0到i2之间;从右侧拉入
- 如果f[i1] > f[i2],则最小值在i1和N之间;从左边拉进来
- 如果f[i1] == f[i2],则最小值在i1和i2之间;从两侧拉入。
算法的运行时间为O(log N)。
关于C# 计算每个给定范围的函数最小值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42473711/