54
правки
Изменения
Нет описания правки
Время работы может быть улучшено до <tex>O(\min(n, m) \cdot \log(\max(n \cdot m))</tex>. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот.
Существует еще один способ оптимизации. Рассмотрим случай, когда используется двоичный поиск по строке. Достаточно очевидно, что искомое число может находится только в тех строках, где первый элемент меньше искомого, а последний — больше. Перед началом поиска можно исключить 2 два прямоугольных участка матрицы: первый состоит из строк, у которых последний элемент меньше искомого; второй состоит из строк, у которых первый элемент больше искомого. Используя двоичный поиск, можно найти границы этих участков за <tex>O(\log(n))</tex> для столбцов и за <tex>O(\log(m))</tex> строк.
