Когда есть необходимость отыскать что-либо в отсортированной последовательности данных, на ум сразу же приходит бинарный поиск, работающий за логарифмическое время. Но иногда даже проверенные временем решения оказываются аутсайдерами, уступая место «молодёжи».
Пусть у нас есть таблица NxM, элементы в которой отсортированы по строкам и по столбцам, например, такая:
Нужно уметь максимально быстро находить нужный элемент в данной таблице.
Если использовать бинарный поиск по столбцу, проходясь по всем строкам и за O(1) решать, искать ли в данной строке элемент (или наоборот, проходиться по столбцам и искать по строкам), то получим сложность O(N*logM) операций. Однако для этой задачи есть более красивое решение, работающее за время O(N+M):
1. Начинаем в левой нижней клетке.
2. Если там стоит искомый элемент, то дело сделано и «мавр может уходить».
3. Если искомый элемент больше текущего, идём на шаг вправо (тогда из рассмотрения убирается весь столбец, в котором мы сейчас находимся). Если идти некуда — значит, элемента в таблице нет.
4. Если искомый меньше текущего, идём вверх, убирая из рассмотрения текущую строку. Опять же, если идти некуда, опускаем руки и говорим, что элемент не найден.
5. GOTO 2
Поиск будет идти, например, вот так:
Нетрудно понять, что алгоритм имеет линейную сложность, ибо на каждом шаге мы избавляемся либо от строки, либо от столбца, уменьшая одну из размерностей задачи на единицу.
Так что иногда полезно изобретать велосипеды вместо того, чтобы пользоваться проверенными решениями:).
P.S. Задача и алгоритм взяты из серии A Programming Job Interview Challenge. Там же есть множество других интересных задачек.
Пусть у нас есть таблица NxM, элементы в которой отсортированы по строкам и по столбцам, например, такая:
Нужно уметь максимально быстро находить нужный элемент в данной таблице.
Если использовать бинарный поиск по столбцу, проходясь по всем строкам и за O(1) решать, искать ли в данной строке элемент (или наоборот, проходиться по столбцам и искать по строкам), то получим сложность O(N*logM) операций. Однако для этой задачи есть более красивое решение, работающее за время O(N+M):
1. Начинаем в левой нижней клетке.
2. Если там стоит искомый элемент, то дело сделано и «мавр может уходить».
3. Если искомый элемент больше текущего, идём на шаг вправо (тогда из рассмотрения убирается весь столбец, в котором мы сейчас находимся). Если идти некуда — значит, элемента в таблице нет.
4. Если искомый меньше текущего, идём вверх, убирая из рассмотрения текущую строку. Опять же, если идти некуда, опускаем руки и говорим, что элемент не найден.
5. GOTO 2
Поиск будет идти, например, вот так:
Нетрудно понять, что алгоритм имеет линейную сложность, ибо на каждом шаге мы избавляемся либо от строки, либо от столбца, уменьшая одну из размерностей задачи на единицу.
Так что иногда полезно изобретать велосипеды вместо того, чтобы пользоваться проверенными решениями:).
P.S. Задача и алгоритм взяты из серии A Programming Job Interview Challenge. Там же есть множество других интересных задачек.