Eu estive pensando sobre essa questão dos trabalhos de casa há um tempo. Dada uma matriz numérica de tamanho n, projete um algoritmo que encontre os valores alto e baixo com no máximo 1,5n comparaçõe

Minha primeira tentativa foi

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]

}

Meu problema é que cada iteração do loop tem uma de três possibilidades:

alor baixo @ encontrado - 1 comparação feitaalor alto @ encontrado - 2 comparações feitas nenhum dos dois é encontrado - 2 comparações feitas

ortanto, para uma travessia inteira da matriz, é possível fazer no máximo 2n comparações, o que está muito longe do requisito máximo do problema de 1,5n nas comparaçõe