python - 如何递归搜索列表中的最大值

Question

我是 python 和算法的新手，我遇到了一个定义如下的问题:

假设给你一个 python 列表 l尺寸n其中仅包含数字。我们索引l从 0 到 n-1 .此外，我们假设存在一个索引 k ∈ {1, ..., n-2}这样

• 所有i ∈ {0, ..., k-1} , l[i] < l[i+1]
• 所有i ∈ {k, ..., n-2} , l[i] > l[i+1]

换句话说，l 是单峰的。 k=3 的示例如下所示:

l = [-5, 8, 12, 15, 13, 12, 10, 5, 1, 0, -2]

我可以使用迭代方法轻松实现它:

def findK(l):
    k = 0
    while l[k] < l[k + 1]:
        k += 1
    return k

但是我如何使用 O(logn) 的递归方式来做到这一点？

Answer 1

利用三元搜索的概念可以得到单峰函数的最大值/最小值

def ternarySearch(f, left, right, absolutePrecision):
    '''
    left and right are the current bounds; 
    the maximum is between them
    '''
    if abs(right - left) < absolutePrecision:
        return (left + right)/2

    leftThird = (2*left + right)/3
    rightThird = (left + 2*right)/3

    if f(leftThird) < f(rightThird):
        return ternarySearch(f, leftThird, right, absolutePrecision) 
    else:
        return ternarySearch(f, left, rightThird, absolutePrecision)

解决方案的总体复杂度为 O(log₃N)。您可以从 https://www.hackerearth.com/practice/algorithms/searching/ternary-search/tutorial/ 了解更多信息或 https://en.wikipedia.org/wiki/Ternary_search