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

如果函数只有一个最小值，使用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)。