Noh*_*sib 1 java algorithm data-structures
给定一个数组,其中值只是增加或只是减少或增加然后减少,如何找到这样和数组的最大值和最小值？
最小值只是最小值的最小值.
但如何找到最大值？
一种方法是运行时间为O(n)的线性方法,可以在O(logn)中使用二进制搜索的一些修改来解决吗？
任何代码(在java中)都非常感激.
谢谢
Nohsib
在斜率从最大增加到最多减少一次的情况下,当导数首先变为负时,最大值出现.换句话说,x[i]是i满足最小值的最大值(x[i+1] - x[i]) < 0.
您确实可以通过二进制搜索O(log n)及时找到它.在每次迭代时,检查导数是否为负数.如果是,则向左移动,否则向右移动.