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

Задача:

Дана матрица, в которой отсортированы все столбцы и строки. Требуется найти заданный элемент [math]x[/math].

Варианты решения

Наивное решение

Описание алгоритма

Нам известно:

• Если первый элемент столбца больше [math]x[/math], то [math]x[/math] находится в колонке слева.
• Если последний элемент столбца меньше [math]x[/math], то [math]x[/math] находится в колонке справа.
• Если первый элемент строки больше [math]x[/math], то [math]x[/math] находится в строке, расположенной выше.
• Если последний элемент строки меньше [math]x[/math], то [math]x[/math] находится в строке, расположенной ниже.