54
правки
Изменения
Нет описания правки
|definition = Задана двумерная матрица, состоящая из n строк и m столбцов. Необходимо найти расположение указанного элемента в матрице или определить, что данный элемент в матрице отсутствует.
}}
== Решение за O(n<tex>\cdot</tex>m) ==
Для начала рассмотрим наивный алгоритм поиска элемента. В каждой строке исходной матрицы запускаем линейный поиск, если находим элемент, то возвращаем его координаты <tex>(row, col)</tex>. Время работы — <tex>O(n \cdot m)</tex>.
== Решение за O(n<tex>\cdot</tex>log(m)) ==
Данный способ решения использует наивное решение за <math>n \cdot m</math>, улучшенное с помощью [[Целочисленный двоичный поиск|двоичного поиска]]. Для этого в каждой строке запускается двоичный поиск. Время работы — <tex>O(n \cdot log(m)</tex>.
'''Замечание'''
Время работы может быть улучшено до <tex>O(min(n, m) \cdot log(max(n \cdot m))</tex>. Для этого необходимо модифицировать алгоритм так, чтобы в том случае, если столбцов больше чем строк, он бы запускал двоичный поиск по строкам, если строк больше — наоборот.
