Algorithme pour trouver les nombres hauts / bas avec au plus 1.5n comparaisons

J'ai pensé à cette devoirs question pour un peu maintenant. Compte tenu d'un certain nombre de tableau de taille n, la conception d'un algorithme qui permettra de trouver de la haute et de et de faibles valeurs d'au plus 1,5 n comparaisons.

Mon premier essai était

int high=0
int low= Number.MaxValue //problem statement is unclear on what type of number to use
Number numList[0 . . n] //number array, assuming unsorted

for (i=0, i < n, i++) {
  if (numList[i] > high)
    high = numList[i]

  else if (numList[i] < low)
    low = numList[i]

}

Mon problème est que chaque itération de la boucle a l'une des trois possibilités:

  • de faible valeur est trouvé - 1 comparaison faite
  • haute valeur est trouvé - 2 comparaisons
  • n'est trouvé - 2 comparaisons

Donc pour un tableau d'ensemble de la traversée, un maximum de 2n comparaisons peuvent être faites, ce qui est loin d'être le problème exigence maximum de 1,5 n comparaisons.

source d'informationauteur Jason