Я немного подумал об этом домашнем задании. Учитывая числовой массив размера n, спроектируйте алгоритм, который найдет верхние и нижние значения с максимум 1,5n сравнениями.

Моя первая попытка была

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]

}

Моя проблема в том, что каждая итерация цикла имеет одну из трех возможностей:

найдено низкое значение - сделано 1 сравнениенайдено высокое значение - сделано 2 сравненияни один не найден - сделано 2 сравнения

Таким образом, для обхода всего массива можно сделать максимум 2n сравнений, что далеко от проблемы максимального требования 1,5n сравнений.