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

Question

我有一个值列表，它增加到最大值然后再次减少（这是观察到的 gaussian/bell-shaped 分布）。

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];

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

hill climbing or a variant of binary search 等解决方案应该有效。步数最少的算法是什么？

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

Answer 1

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

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

Answer 2

正如 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

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

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

Answer 3

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

基本上，从

开始

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)

渐近地，这是您在不依赖值的某些属性的情况下可以做的最好的事情。如果不是 "good enough"，请更改 low 和 high 的表达式以更好地匹配您的真实数据。

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

Fast algorithm for finding maximum in a bell-shaped list of values

algorithm

binary-search

hill-climbing