Постановка задачи.
Дана матрица N на M с произвольными числами и тем свойством, что значения чисел в каждой строке не убывают, а в каждом столбце не возрастают
Задача определить, есть ли в матрице заданный элемент A.
Для начала, если вы не слышали об этой задаче прежде, попробуйте найти для нее решение за O(N+M).

Далее решение Алисы:
Задачу можно решить за O(log S * log S), где S - это максимум из ширины и высоты матрицы, следующим образом: возьмем нашу матрицу, без потери общности допустим, что ширина больше высоты. Возьмем средний столбец, и бинарным поиском будем искать А. Мы можем прийти к одному из трех случаев (не учитывая случай, что мы нашли А - тогда все очевидно):
1. Все элементы в столбце больше А, то есть бинарный поиск сошелся на самом нижнем элементе и не нашел А. Так как значения в строках возрастают, очевидно, что правее этого стобца все числа также больше А, а значит дальше имеет смысл рассматривать только левую половину матрицы.
2. Все элементы в столбце меньше А. Аналогично, только отбрасываем левую половину и повторяем решения для правой половины.
3. В столбце есть как элементы больше, так и элементы меньше. Бинарный поиск в конце концов остановился на какой-то ячейке, значение которой меньше А, такой, что прямо над ней находится ячейка, значение в которой больше чем А. Тут очевидно, что все элементы левее и ниже этой ячейки меньше А, а все элементы правее и выше - больше, то есть мы можем отбросить все, что левее и ниже или правее и выше. Можно понять, что при этом будет отброшена не менее чем половина всех элементов (можно нарисовать, чтобы понять почему - грубо говоря, в каждой строке будет отброшена либо левая половина, либо правая - так как в каждой строке будет отброшена хотя бы половина, то и в целом по матрице будет отброшена хотя бы половина).
Таким образом, не зависимо от обстоятельств, хотя бы половина элементов матрицы будет отброшена, а значит нам надо выполнить не более log(S) шагов, на каждом из которых мы выполним один бинарный поиск, сложность которого O(log(S)), таким образом общая сложность решения - O(log S * log S).

Опровержение Боба:
Построим квадратную матрицу, в которой все элементы выше не главной диагонали равны +oo, все элементы ниже не главной диагонали равны -oo, а все элементы на этой самой не главной диагонали равны случайным числам. Эта матрица удовлетворяет условию задачи. Совершенно очевидно, что если бы в такой матрице можно было найти заданный элемент быстрее, чем за линейное время, то для произвольного массива из N элементов можно было бы найти заданный элемент быстрее, чем за линейное время, а это не правда. Значит решения быстрее чем за линейное время быть не может.

Так кто же ошибается, Алиса или Боб?