在递增、递减、递增和递减数组中查找最大值和最小值的算法

Question

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

最小值只不过是最终值中的最小值。

但如何找到最大值呢？

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

任何代码（java）都受到高度赞赏。

谢谢
诺赫西布

Answer 1

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

您确实可以通过二分搜索在 O(log n) 时间内找到它。在每次迭代时，检查导数是否为负。如果是则向左移动，否则向右移动。

Answer 2

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 3

通过二分查找，看看属于哪种情况。本质上，尝试找到第一个枢轴点，其中有较大的元素，紧接着较小的元素，例如 p1，以及第一个枢轴点，其中有较小的元素，紧接着较大的元素，例如 p2。您可以使用二分搜索（谷歌在旋转排序数组中进行二分搜索）来完成这些操作，

如果 p1 存在 p2 不存在，则它是一个递增序列（min = a[0] max=a[n]）

如果 p2 存在而 p1 不存在，其递减序列(min = a[n] max=a[0])

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

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

Answer 4

订单统计树将做你想要的。它可以在 O(lgn) 中找到任何阶统计量，包括最小值和最大值。形成树的成本为 O(nlgn)，这与最佳比较排序的复杂度相同。添加或删除元素的成本也为 O(lgn)。

这是一个链接（OrderStatisticTree.java）顺序统计树的java实现。

然而，考虑到您所陈述的假设，正如您所指出的，可以在 O(1) 中找到最小值。最大值可以在 O(lgn) 中找到。这是伪代码：

findMax(array,n,m)
  middle = (n + m) / 2;

  //check for short array (length 1 or 2) to avoid indexing errors
  if middle == n && array(middle) > array(m)
    return(array(middle));
  else
    return(array(m));

  if array(middle) > array(middle - 1) //left side of peak
    if array(middle) < array(middle + 1) //at peak
      return(array(middle));
    else
      return(findMax(array(middle,m)); //peak is to the right
  else //right side of peak
    return(findMax(array,n,middle); //peak is to the left

Answer 5

根据 Jean-Bernard Pellerin 建议的逻辑

（此代码中仅找到最大值）

public class max_in_increasing_decreasing_array 
{
    public static int max (int a,int b,int c)
    {

    int maxi=-1;

    if(a>maxi)
        maxi=a;
    if(b>maxi)
        maxi=b;
    if(c>maxi)
        maxi=c;


    return maxi;
}
public static void chkmax(int a[],int low,int high)
{
    int mid=(low+high)/2;
    if(low==high)
    {
        System.out.println(a[low]);
        return;
    }
    if(low+1==high)
    {
        System.out.println(max(a[low],a[high],-1));
        return;
    }

    if((a[mid-1]< a[mid]) && (a[mid] < a[mid+1]))
    {
        chkmax(a, mid+1, high);

    }
    else if((a[mid-1]> a[mid]) && (a[mid] > a[mid+1]))
    {
        chkmax(a, low, mid-1);

    }
    else
        System.out.println(max(a[mid-1],a[mid],a[mid+1]));
}

public static void main(String[] args) 
{
    int a[]={6,7,4,3,2,1};
    chkmax(a, 0,a.length-1);
}

}