algorithm - 在钟形值列表中找到最大值的快速算法

Question

我有一个值列表，这些值增加到最大值然后再次减小（这是观察到的高斯/钟形分布）。

values = [0, 4, 5, 15, 30, 20, 10, 5, 0];

但分布也可以改变：

values = [0, 0, 0, 1, 2, 3, 8, 15, 30];

或类似地：

values = [30, 20, 5, 2, 1, 1, 0, 0, 0];

在此特定应用程序中，确定特定索引处的值非常昂贵，因此使用尽可能少的数组查找非常重要。

诸如爬山或二进制搜索的变体之类的解决方案应该可以工作。步骤最少的算法是什么？

长查找时间是由于真实世界的测量设备（时间以秒为单位）。

Answer 1

假设您没有局部最大值（因为它通常会在测量中发生），二进制查找是最快的方法。例如，如果您有 1000 个数据点，那么在最坏的情况下，当最大值位于中间某个位置时，您最终会进行大约 10 次检查。

为了应对最大值位于数据右侧或左侧的情况（例如在第二个和第三个示例中），您可以简单地检查两端中的任何一个是否高于其连续点，如果确实如此，您最终的搜索结果不超过两次检查。

Answer 2

您正在寻找三元搜索，可能使用插值搜索的一些启发式方法。

基本上，从

def search(f, begin, end):
    if end - begin <= 3:
        return max(map(f, range(begin, end)))
    low = (begin * 2 + end) / 3
    high = (begin + end * 2) / 3
    if f(low) > f(high):
        return search(f, begin, high - 1)
    else:
        return search(f, low + 1, end)

渐近地，在不依赖值的某些属性的情况下，这是您能做的最好的事情。如果它不是“足够好”，请更改表达式以更好low地high匹配您的真实数据。

Answer 3

正如 FDavidov 所提到的，您应该使用二进制搜索的变体，因为您只需要ceil[O(logn)]在最坏的情况下访问索引。

二进制搜索变体的伪代码如下所示：

left := 0
right := n - 1
while left < right do
    mid := left + (right - left) / 2
    if values[mid] > values[mid + 1] 
         right := mid
    else
         left := mid 
end

print left

但是，要在非凸形图中找到最大或最小点，三元搜索效果最好。但是三元搜索基于一些不适合整数的非整数评估函数来削减空间。

如果您不需要精确的结果并且可以接受近似值，您也可以尝试三元搜索。