Programming Pearls Проблема: проверка отсортированного массива в двоичном поиске

В Programming Pearls (второе издание), столбец 5, проблема 5 вопрос касается реализации двоичного поиска в несортированном массиве.

Как добавить частичную проверку в функция при значительно меньших чем стоимость O (n-1)?

Я знаю, что вы можете проверять каждую итерацию и достигать O (log n), но подсказка на обратной стороне предполагает, что существует решение O (1).

Что это за решение?