求递增、递减、递增和递减数组中最大值和最小值的算法

Question

给定一个数组，其中的值要么只增，要么只减，或者先增后减，如何找到这样的数组的最大值和最小值？

最小值只是最小的终结值。

但是如何找到最大的价值呢？

一种方法是运行时间为O(n)的线性方法，这可以在O(logn)中解决吗，使用对二进制搜索的一些修改？

任何代码(在java中)都是非常受欢迎的。

谢谢

诺希布

Answer 1

if [1] < [2]
  if [end-1] < [end]
    min = [1]
    max = [end]
  else
    min = min([1],[end])
    max = binarysearch()
else
  min = [end]
  max = [1]

binarysearch:
take the middle element [mid]
if [mid-1] < [mid] < [mid+1]
  binary search [mid - end]
else if [mid-1] > [mid] > [mid+1]
  binary search [start - mid]
else
  return max([mid-1],[mid],[mid+1]

Answer 2

在斜率从增加到减少最多一次的情况下，最大值出现在导数第一次变为负值时。换句话说，x[i]是满足(x[i+1] - x[i]) < 0的i的最小值的最大值。

你确实可以在O(log n) time中通过二进制搜索找到这一点。在每次迭代中，检查导数是否为负。如果是，则向左移动，否则向右移动。

Answer 3

通过二进制搜索，看看它属于哪种情况。重要的是，试着找到第一个轴心点，在那里有更大的元素，紧接着是较小的元素，比如p1，和第一个轴点，有一个更小的元素，紧跟着更大的元素，比如p2。您可以使用二进制搜索(google用于旋转排序数组中的二进制搜索)来实现这两个功能

如果p1存在p2不存在，则它是一个递增序列(min =a max=an)

如果p2存在而p1不存在，则其为递减序列(min= max=a)

如果两者都存在，则其增加和减少

min = min(a[0],a[n]) \\first and last
max = a[p1] \\first point where bigger element is followed by a smaller one