Алгоритм поиска высоких / малых чисел с максимумом 1,5n сравнений

Я немного подумал над этим домашним заданием. Учитывая числовой массив размера 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 сравнений.