使用二进制搜索查找函数的最大值

一旦您将数组中的输入数从0扩展到n,函数似乎是一个递增/递减/递增然后递减的数组。您可以使用二进制搜索来查找函数中的峰值。对于每个中点,您可以确定阵列的部分是在减少、增加还是达到峰值,然后定位阵列的哪个部分可能具有峰值。您可以在中找到更多详细信息和解释 this article

int maxInBitonic(int arr[], int low, int high)
{
    // find out the size of the array
    // for edge case checking
    int n = high + 1;

    // main code goes as follows
    while (low <= high) {
        // find out the mid
        int mid = low + (high - low) / 2;
        
        // if mid index value is maximum
        if(arr[mid] > arr[mid+1] and arr[mid] > arr[mid-1])
            return arr[mid];

        // reducing search space by moving to right
        else if (arr[mid] < arr[mid + 1])
            low = mid + 1;

        // reducing search space by moving to left
        else
            high = mid - 1;
    }

    return arr[high];
}

不幸的是,我不熟悉C++来帮助您编写代码,但以下几点可能会有所帮助。

1. 检查函数的梯度并朝同一方向移动怎么样。由于你的函数(正如你所描述的)只有一个极大点,我认为这是正确的方法。

2. 坡度计算: grad(x1 - x2) = (f(x1) - f(x2))/ (x1 - x2)

3. 应用二进制搜索来限制搜索域。所以如果你检查一下 0 和 1 例如,这是积极的。然后我们沿着梯度移动到右侧,因为我们知道函数正在增加,移动到 1. 。然后我们将搜索转移到 1. 和 2^64 - 1 ,将搜索领域一分为二。冲洗并重复。

4. 所以,如果我们继续这样做,在某个点上,我们要么达到0的梯度,要么达到非常小的梯度值( ~0 ),甚至你的梯度值也可以在负和正之间振荡,这意味着你接近局部的max/min(但在我们函数的情况下,它是一个max)。在这里,如果需要,您可以手动调整搜索以更快地收敛到最终结果。或者只是决定在一个估计值上停止。

5. 但既然你在做二进制搜索,我认为它无论如何都会很快收敛。在我们不知道域大小的情况下,梯度偏心通常需要步骤4。然而,在这种情况下,有一个域大小和二进制搜索是很适合的。

希望得到帮助,祝你工作顺利!