寻找局部最高点-1D

一种方法是从第一个元素逐个开始遍历。算法复杂度为 T=O(n)。

另一种算法使用二分法。对于一个点，有以下情况：

• 两边小（此时是局部最高点）（暂时不考虑相等的情况）；
• 左边小右边大，此时局部最高点一定出现在右边，可以继续在右边继续寻找；
• 左边大右边小则在左边继续寻找
• 两边大，局部最高点出现在两边，向左向右都可以。
  此算法时间复杂度为 T=O(log2​n)。

代码如下：

\"\"\"
@author: LiShiHang
@software: PyCharm
@file: 1.寻找局部高点-1D.py
@time: 2018/12/3 18:01
\"\"\"


def find_local_highest_location2(a):

    if len(a) == 1:
        return 0
    if len(a) == 2:
        return int(a[0] < a[1])

    middle = len(a) // 2

    if a[middle - 1] < a[middle] > a[middle + 1]:
        return middle

    elif a[middle - 1] > a[middle]:
        return find_local_highest_location2(a[:middle])

    else:
        return middle + 1 + find_local_highest_location2(a[middle + 1:])


if __name__ == \'__main__\':
    # A = [1, 5, 2, 3, 4, 0]
    import numpy as np
    A=np.random.randint(0,100,10).tolist()
    i = find_local_highest_location2(A)
    print(A)
    print(i)