peak finding 问题

date
Nov 16, 2022
slug
peak-finding
status
Published
tags
算法
summary
如何高效找到峰值？Divide & Conquer
type
Post
出处分析1D finding2D findingMIT讲义总结参考延伸

出处

《算法》上面1.4.18，1.4.19两道题目
notion image
这两道题目就是 peak finding 问题，找到局部最大/局部最小元素的问题其实是等价的。如果你只写了找到局部最大的元素算法，现在想要找局部最小的元素，那么只需要把a中的元素都乘上-1就行了。
另外请注意我们讨论的数组是distinct的，如果有重复数字，的算法是实现不了的

分析

暴力法很容易写出， check 一遍就行了
但是我看到提示 答：检查数组的中间值 a[N/2] 以及和它相邻的元素 a[N/2-1] 和 a[N/2+1]。如果 a[N/2] 是一个局部最小值则算法终止；否则则在较小的相邻元素的半边中继续查找。感觉很迷惑，这个在较小的相邻元素里面的半边继续查找的依据是什么？不会漏掉正确答案吗？
看了一些资料以后发现上述两道题目叙述得其实不完整，上面题目没有对边界条件进行说明，导致我以为要找的元素下标必须满足i∈[1,length-1] ，完整的题目应该是：对于边界元素，它只需要小于相邻的边界元素，那么这个边界元素就是局部最小的。
我们先看一般的情况吧，对于任意一个数列，我们从随机的位置开始寻找局部最小
那么情况可以穷举出来
  1. 当前元素就是局部最小
  1. 当前元素不是局部最小，那么此时，总是会有一边以上的元素小于当前元素。可以自己写一下各种情况
看图，图片里面是找局部最大，不过没有关系，思想是一样的，这里是总有一边以上的元素会大于当前元素
notion image
那么上面的提示也说得通了，对于1 2 3 4 5 6 7 5这种组合，N=8，A[N/2]=5 第一次判断的元素是5，4<5<6，4比6小，那么会往左边查找，查找过程中它只有两种情况
  1. 碰到一个局部最小的元素 我们的任务完成了
  1. 碰到第一个元素 结论：第一个元素一定是局部最小的元素
如果一路上没有碰到局部最优的元素，那么就会走到第一个元素，此时第一个元素必定是局部最小的元素
为什么？递推一下
假设第一个元素不是局部最小的元素，那么a[0]>a[1] 此时a[1]如果不是局部最小的元素，那么a[1]>a[2] ... 此时如果a[N/2-1]不是局部最小元素，那么a[N/2-1]>a[N/2]，矛盾的地方出现了
回到这个例子上，我们之所以往左边找，就是因为a[N/2-1]<a[N/2]
这说明我们如果走到了第一个元素，那么第一个元素一定是局部最小的
可能你会怀疑，这只是一边的情况，其实你往右推导也是一样的
进一步可以得出结论，如果a[j]不是局部最小的元素，那么总有一边的相邻元素会小于a[j]，由上结论得：
我们一定可以在较小的相邻元素那边找到一个局部最小的元素
上述结论要求数组是distinct的

1D finding

暴力法很容易写出，O(N) 加了一些边界条件让算法更稳定。伪代码会更简洁
现在我们有了上述的理论，可以优化算法了，很容易想到二分的思想
由于一些边界情况的判断，写得比较丑陋，可以把上面改写成递归的形式，下面是python代码 需要注意的是递归传递数组是子数组，要用base变量来记录当前子数组的正确起始下标
当然也可以不传递子数组，而是每次递归传递整个数组，然后更改lo,hi两个变量来表示搜索的区间
时间复杂度现在降为$O(logN)$了，分析请看下图，每次一迭代都问题规模变成一半
notion image
当子问题的规模等于$n/2^k$的时候，我们设$n=2^k$，那么就能推出来这是O(lgn)的算法

2D finding

notion image
再延伸一下，从数组扩展到二维矩阵，同样是找局部最小元素 同样2D-finding问题的暴力法也很容易写出，遍历每个元素即可
但是有了1D-finding问题的推论，我们期望找到一个比暴力法更优的解法，接下来尝试一下能不能找到$O(N)$级别的算法
一个简单的想法就是，对于M=N*N的矩阵，我们一开始找到第M/2个元素，查看它是否满足局部最小，如果满足则返回，如果不满足则在相邻元素之间找到最小的元素，然后以它在矩阵中的位置为新的界限，继续执行二分算法，知道找到第一个满足局部最小的元素
更具体的做法，不考虑边界情况，如果某个元素的左或者上元素更小，那么这个更小元素的位置更新为上界，继续迭代，如果某个元素的右或者下元素更小，那么就以这个更小元素的位置更新为下界，继续迭代
由此我们可以写出以下代码
测试用例以及运行结果
func2不能传递空数组，会throw Error，而func2(D)的运行结果是1 从结果来看，func2的写法似乎正确，但我不确定这是不是最优的算法，因为上面我写的版本有一些凌乱，下面是MIT的6.006课程讲义上的解法

MIT讲义

注意MIT讲义上面是找局部最大，一种方法是找出矩阵的每一列，然后把每一列的最大元素拼接在一起，再用1D-finding的解法去找局部最大，不过这样做的时间复杂度是
notion image
下面是第四种写法
notion image
slide上面说得不太清楚，我再叙述一下
  1. 选择中间的列作为起点，找到该列最大的元素，位于i,j
  1. 比较
  1. 如果比大，那么就选择左列然后重复上述步骤
  1. 如果比大，那么就选择右列然后重复上述步骤
  1. 如果最大，那么它就是答案
上面递归的边界情况就是递归到只剩下一列，同理我们可以推导这一列里面一定存在一个最大的元素，使得它是局部最大的，所以这个算法能成立，寻找最大元素的复杂度是N，二分的过程是logn，这个算法的时间复杂度是 那么根据上面的分析可以写出代码
然后是最后一个解法，这个算法的时间复杂度是级别的
notion image
不过这个解法课程视频上没有说，我另外在youtube上找了其它视频来看，不过好像也没有提到这种解法，似乎是课后习题，这里就不写了。

总结

本文引入了 distinct 的 peak finding 问题，从一个简单的例子分析出了 peak finding 特有的性质。在 1D finding 的基础上扩展到了 2D finding 问题。
可以看到 解法的思想着重体现在分治上面，如果我们能找到某条路径使得每次问题规模缩减一半，那么这个解法就是 的。

参考

感谢这位作者维护的repo https://github.com/reneargento/algorithms-sedgewick-wayne/blob/f31578352b7774e857a664bf8768bca2200e75e0/src/chapter1/section4/Exercise18_LocalMinimum.java
mit的讲义 extension://bfdogplmndidlpjfhoijckpakkdjkkil/pdf/viewer.html?file=http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf 配套课程是 https://www.youtube.com/watch?v=HtSuA80QTyo
SO上的答案 https://stackoverflow.com/questions/12238241/find-local-minima-in-an-array
主定理 https://zh.wikipedia.org/wiki/主定理https://blog.csdn.net/woshilsh/article/details/89429130
力扣上面相似的题目 https://leetcode-cn.com/problems/find-peak-element/https://leetcode-cn.com/problems/search-a-2d-matrix/https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/
力扣的题解和文章上面的思路略有不同，不过结果都是一样的

延伸

关于上面三道leetcode，额外写了文章汇总 https://blog.csdn.net/hhmy77/article/details/108193937
 

© hhmy 2019 - 2024