一組元素中的同時最大值和最小值

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]處找到最小值。或者反過來降序排列。