一组元素中的同时最大值和最小值

Question

在Sec-9.1中提到的书“Intro to algorithm-by CLRS”中，可以在运行时间3 * floor（n/2）中同时执行最大值&最小查找。同样也是下界。

我写了下面的算法（从CLRS获得帮助），它的下界是2 * floor（n/2）。 [这是错误的---由于瑞奇·鲍比]

I m using the variables: 'max' & 'min' to denote maximum & minimum elements, 'i' as indexing variable. 

Simultaneous_Maximum_&_Minimum (A, n) // Array A[1...n] 
{ 
    1. If n is even, compare the first two elements and assign the larger to max and 
     smaller to min. Set StartIndex = 3. 

    2. If n is odd, set both max & min to the first element. Set StartIndex = 2. 

    3. for (i = StartIndex; i <= n; i = i+2) { // Processing elements in pair 

     if (max < A[i]) {   // Compare max with A[i] 
       if (A[i] < A[i+1]) // Compare max with A[i+1] 
        max = A[i+1]; // we sure that A[i] or A[i+1] can't be min 

       else {     // When max less than A[i] but A[i] not less than A[i+1] 
        max = A[i];  // Set A[i] as max 
        if (min > A[i+1]) // Possible that A[i+1] can be min 
          min = A[i+1]; // if yes, set A[i+1] as min 
       } 
     } 

      // When max is not less than A[i] 
     else if (min > A[i]) {  // Compare min with A[i] 
        if (A[i] > A[i+1]) // Compare min with A[i+1] 
          min = A[i+1]; // we sure that A[i] or A[i+1] can't be max 

        else {    // When min is greater than A[i] but A[i] not greater than A[i+1] 
          min = A[i];  // Set A[i] as min 
          if (max < A[i+1]) // Possible that A[i+1] can be max 
           max = A[i+1] // if yes, set A[i+1] as max 
        } 
       }      
     } 

     else { // max > A[i] and min < A[i] -- so A[i] can't be max or min 

       if (max < A[i+1]) 
        max = A[i+1] 

       if (min > A[i+1]) 
        min = A[i+1] 
     } 
    } 
} 

感谢瑞奇·鲍比指出我的错误 - 我们不能做2查找同时最大&最小*地板（N/2）运行时间。

Answer 1

告诉我，如果我错了，但你不看情况：最大> A [1]>分钟

if max>A[i]>min : 
    if A[i+1] > max 
     max =A[i+1] 
    if A[i+1] <min 
     min = A[i+1] 

那么你的算法是错误的一般情况。

降序或升序它可能工作，但它是相当无用的，因为对于一个排序列表，你可以找到的最小值和最大值此espression：

(min,max) = (A[0],A[n]).sort() 

所以在O（获得（A [0 ]）+ get（A [n]））

Answer 2

如果数组已排序，则可以在数组[0]处找到最小值，并在数组[n-1]处找到最小值。或者反过来降序排列。