Algorithm

求一个数组的波峰

三个月前被问到一个有趣的算法题，当时想了很久才想出来，现在写篇博客记录一下。

给定一个很长的数组 arr，已知数组的长度 length 且 length >= 3，已知数组的第一个元素不比第二个元素大，最后一个元素不比倒数第二个元素大。那么求这个数组中 任意一个 波峰的数组下标。PS：不比前一个元素小而且不比后一个元素小的元素称为波峰。

arr[1] >= arr[0]，那么只需要 arr[1] >= arr[2] 1 就是一个波峰了。

如果 arr[1] < arr[2] ，那么只需要 arr[2] >= arr[3] 2就是一个波峰了。

……

这个其实可以抽象成一个动态规划的问题。但没必要而且很明显抽象之后还是得遍历…

等等…如果除去第一个元素和最后一个元素的数组是一个有序递增的数组怎么办，这种情况下我们需要扫遍整个数组，从而付出 O(N) 的复杂度。有没有觉得这个有点像连环诈骗，指针每次移动到的元素都满足波峰的前一部分条件（不比前一个元素小），我们满心欢喜地期待它满足下半部分的条件，但是有时候并不能如愿。

有没有那么一瞬间想到二分搜索？

确实，这个很像二分搜索可以解决的问题。但是 数组并没有说自己有序啊。所以根本不满足二分搜索的基本条件。

死马当活马医看下？

好吧，那么我们试一下。我们在数组的正中间取一个元素，我们称为 arr[length/2]。
取到之后，我们是不是应该满怀希望地迫不及待地将它和它的左右两个元素进行比较呢？因为这个比较发生在数组上，所以开销可以忽略不计。
如果它比左右都大，那很明显它就是一个波峰，那这个时候返回它的下标 length/2 就可以了。
那如果它比左边的小或者比右边的小，或者比左右都小呢？
那么波峰是不是可以在左边或者右边找一找，如何确定左边或者右边一定有波峰呢？

这个时候，我们应该注意到两个问题。

  1. 如果它比左边的小，那么 arr[:length/2+1] 这个子数组也是一个符合题设条件数组。如果它比右边的小，那么 arr[length/2:] 这个子数组也是一个符合题设条件数组。
  2. 在左边找或者在右边找一定能找到一个波峰吗？换句话说，符合提设条件的数组是否一定存在至少一个波峰？

如果注意到这两个问题，那么这道题就迎刃而解了。
给出实例代码（纯手写…）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def find_peak(arr, length):
    if length < 3:
        return -1

    middle = length / 2
    if length < 4:
        return middle 
    
    if arr[middle] > arr[middle - 1] and arr[middle] > arr[middle + 1]:
        return middle
    if arr[middle] < arr[middle - 1]:
        return find_peak(arr[:middle + 1], middle + 1)
    sub_length = middle + 1
    if length % 2 == 0:
        sub_length = middle
    return find_peak(arr[middle:], sub_length)

这个代码实现需要考虑非常多的边界，也许我的代码还没考虑到，如果有问题，欢迎拍砖。

Share