C# 计算每个给定范围的函数最小值

Question

我需要在没有运行 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;
    }

在第一个数组中有效，但在第二个和第三个数组中无效。我在这里错过了什么？

Answer 1

我通常讨厌回答作业问题，但我有点喜欢这个。

首先，认为这两个 "diagonal" 情况没什么特别的，只是对夸张的不同看法，其中最小值恰好在边缘。

然后，尝试使用二进制搜索之类的方法来找到最小值。看一眼中间的两个元素，看看它们之间的关系，然后决定最小值在哪一边。重复直到只剩下一个元素。

Answer 2

如果函数只有一个最小值，使用Ternary Search:

ternary search algorithm is a technique for finding the minimum or maximum of a unimodal function.

想法是将范围分成三个相等的部分，探测两个搜索点，然后 "pull in" 不包含最小值的那个。假设搜索点i1在区间左侧，i2在区间右侧：

如果f[i1] < f[i2]，则最小值在0到i2之间；从右边拉入
如果f[i1] > f[i2]，则最小值在i1和N之间；从左侧拉入
如果f[i1] == f[i2]，则最小值在i1和i2之间；从两边拉进来。

算法的运行时间为O(log N)。

C# 计算每个给定范围的函数最小值

C# calculate function min per given range

c#

arrays

graph-theory