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

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

在这个特定的应用程序中，确定特定索引处的值非常昂贵，因此使用尽可能少的数组查找非常重要。可以使用爬山算法或二分查找的变体等解决方案。哪种算法步骤最少？由于实际测量设备的原因（时间为几秒钟），查找时间较长。

- Yeti

---

使用数组数据结构重要吗？ - Alex Aparin

不一定，它也可以是一个未知的函数 f(x)，对于给定的 x 值进行测量。这类似于具有离散值输入数组 x 和输出数组以获取结果的情况。你为什么问呢？ - Yeti

我的想法是使用二叉搜索树，使得根节点始终为最大值。这可以优化查找最大值的过程。 - Alex Aparin

Answer 1

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

为了应对最大值位于数据左侧或右侧的情况（例如第二个和第三个示例中的情况），您可以简单地开始检查两端是否高于相邻点，如果是，则最多进行两次检查即可结束搜索。

- FDavidov

---

你的算法没有考虑到重复元素。如果你落在一个由46个相同元素组成的序列中间，为了在只进行10次迭代后完成，你会将mid设置为什么？顺便说一下，我的算法在最大值在两端时也适用。也许你误解了它的实现方式。 - גלעד ברקן

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

然而，要在非凸形状的图形中找到最大或最小点，三分搜索 是最好的选择。但是，三分搜索基于一些非整数评估函数来削减空间，这不适用于整数。

如果您不需要精确结果，接受近似结果，则也可以尝试使用三分搜索。

- Kaidul

---

你的算法伪代码在处理 [0,1,0,0,0,0,0] 时返回了错误的结果。 - גלעד ברקן

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)

从渐进上看，如果不依赖于值的某些属性，这是你能做到的最好结果。如果结果还不够好，尝试改变low和high的表达式以更好地匹配实际数据。

- user2512323

---

我使用了这种方法。实际上，我给它一个参数 k。也就是说，对于 k = 2，它是二分查找，对于 k = 3，它是三分查找，对于更高的 k 值，它只是查看更靠近 begin 和 end 边界的值。此外，对于近似测量，它还可以实现检查 abs(f(low) - f(high)) 是否小于某个值，如果是，则将 low 和 high 都作为 begin 和 end 值。但在我的情况下，这并不是真正必要的。 - Yeti