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

Question

给定一个数组，其中的值只是增加或仅递减或递增然后递减，如何找到这样的最大值和最小值和数组？

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

但如何找到最大值？

一种方法是运行时间为O（n）的线性方法，是否可以在O（logn）中使用二进制搜索的一些修改来解决这个问题？

任何代码（在Java中）高度赞赏。

由于
Nohsib

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)时间用二进制搜索找到它。在每次迭代中，检查导数是否为负数。如果是，则向左移动，否则向右移动。

Answer 3

通过二分法查找，查看它属于哪种情况。 Essentialy尝试找到第一个枢轴点，其中有较大的元素紧跟着较小的p1，并且第一个枢轴点有一个较小的元素，紧接着是较大的元素，如p2。你可以做这些都与二进制搜索（谷歌用于在旋转排序后的数组二进制搜索）

如果P1存在P2犯规，其增加的序列（分钟= A [0] MAX = A [n]）的

如果P2存在和P1犯规，其减小的序列（分钟= 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

一种order-statistic tree会做你所做的蚂蚁。它可以在O中找到任何订单统计信息（包括最小值和最大值）（lg n）。形成树成本成本O（ n lg n），这与最佳比较排序具有相同的复杂度。添加或删除元素也需要O（lg n）。

这是一个链接（OrderStatisticTree.java）到一个订单统计树的Java实现。然而，考虑到你所说的假设，最小值可以在O（1）中找到，正如你已经指出的那样。最大值可以在O中找到（lg n）。这里是pseduo代码：

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

据吉恩 - 伯纳德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); 
} 

}