Поиск элемента в частично отсортированном массиве

У меня был следующий вопрос на собеседовании:

Есть массив из nxn элементов. Массив частично отсортирован, т.е. самый большой элемент в строке i меньше наименьшего элемента в строке i + 1 . Как найти заданный элемент со сложностью O (n)

Вот мой вариант:

Вам нужно перейти к строке n / 2.И начните сравнивать, например, вы ищете 100 и первое число, которое вы видите, это 110, так что вы знаете, что оно либо в этой строке, либо в строках выше, теперь вы набираете n / 4 и т. Д.

Из комментариев

Isn ' итого O (n * log n)? У него есть разбирать каждую строку, которую он достигает за бинарный поиск, поэтому количество линейных поисков умножается на количество строк, которые он сканировать придется в среднем. - Мартин Матысяк 5 минут назад

Не уверен, что это верное решение. Есть ли у кого-нибудь что-нибудь получше