Найти число в отсортированной матрице (строки n столбцов) в O (log n)

Скажем, у меня есть матрица (MxN), которая сортирует свои строки и столбцы.

Все элементы в каждой строке расположены в порядке возрастания
Все элементы в каждом столбце упорядочены в порядке возрастания
Все элементы являются целыми числами
Никакие другие предположения не могут быть сделаны

Пример:

[1 5 8 20]

[2 9 19 21]

[12 15 25 30]

Мне нужно найти, присутствует ли заданное число в матрице или нет (основной поиск). У меня есть алгоритм, который работает O(n)

int row = 0;
int col = N-1;

while (row < M && col >= 0) {
  if (mat[row][col] == elem) { 
    return true;
  } else if (mat[row][col] > elem) { 
    col--;
  } else { 
    row++;
  } 
}

Но мне было предложено решение O(log (MxN)) == O(Log(n)). Любые идеи?

Ответ 1

O (log (M * N)) для этой задачи невозможно.

Посмотрим на упрощенную задачу: в "отсортированной" квадратной матрице предположим, что все элементы выше вторичной диагонали (зеленые) меньше заданного числа, все элементы ниже вторичной диагонали (красные) больше заданного числа, и никаких дополнительных предположений для элементов на вторичная диагональ (желтый).

Ни оригинальные предположения этой задачи, ни эти дополнительные предположения не говорят о том, как элементы вторичной диагонали связаны друг с другом. Это означает, что у нас просто есть несортированный массив из N целых чисел. Мы не можем найти заданное число в несортированном массиве быстрее, чем O (N). Поэтому для исходной (более сложной) задачи с квадратной матрицей мы не можем получить решение лучше, чем O (N).

Для прямоугольной матрицы растяните квадратное изображение и соответствующим образом установите дополнительные предположения. Здесь мы имеем min (N, M) отсортированные подмассивы размером max (N, M)/min (N, M) каждый. Лучший способ поиска здесь - использовать линейный поиск, чтобы найти один или несколько подматриц, которые могут содержать заданное значение, а затем использовать двоичный поиск внутри этих подмассивов. В худшем случае необходимо двоично-поиск в каждом подматрице. Сложность - O (min (N, M) * (1 + log (max (N, M)/min (N, M)))). Таким образом, для исходной (более сложной) задачи с прямоугольной матрицей мы не можем получить решение лучше, чем O (min (N, M) * (1 + log (max (N, M)) - log (min (N, M)))).

Ответ 2

Невозможно сделать лучше, чем O (n). Некоторые ребята (по крайней мере, три из них на этой странице) думают, что они могут сделать лучше, но это потому, что их алгоритмы ошибочны или потому, что они не знают, как вычислить сложность их алгоритма, поэтому они пытаются угадать его. Этот пост в блоге очень хорош и объяснит вам ошибки этих ребят.

Проект доказательства оптимальности O (n): рассмотрим следующую матрицу:

1     2     3     4     5     6 … (n-2)  (n-1) (n+1)
2     3     4     5     6     7 … (n-1)  (n+1) (n+2)
3     4     5     6     7     8 … (n+1)  (n+2) (n+3)
…     …     …     …     …     … … …      …     …
(n-2) (n-1) …     …     …     … … …      …     (2n-1)
(n-1) (n+1) …     …     …     … … …      …     2n
(n+1) (n+2) …     …     …     … … (2n-1) 2n    (2n+1)

Если вы ищете n в этой матрице, вы должны проверять хотя бы один раз для каждой строки, если n находится в строке, потому что n может быть в любой строке. (Доказательство не является полным, но вот идея)

Ответ 3

Вы должны использовать рекурсию для решения этой проблемы. Учитывая матрицу X и число y, вы можете выполнить двоичный поиск y в средней строке X и разделить матрицу на четыре части так, чтобы:

A|B
---
C|D

все элементы в меньше y, все элементы из D больше y, а y может быть в B и C. Итеративно найти y в B и C.

Так как высота (A) = высота (B)\approx = высота (C) = высота (D), размер (X) >= 2 * (размер (B) + размер (C)). Таким образом, полученная сложность, если O (logn).

def find(X,y):
    a,b = X.shape
    i = a /2
    j = binsearch(X[i,:], y)
    if X[i,j]==y:
        return True
    else:
        return find( X[ (i+1):a, 0:(j-1)], y ) or find( X[ 0:i, j:b], y )

Ответ 4

Поскольку как строки, так и столбцы отсортированы, если мы посмотрим на первый элемент каждой строки, мы можем найти, какой из них содержит число, которое мы ищем. Тогда, опять же, мы можем использовать тот факт, что элементы в каждой строке сортируются и находят это число.
Самый быстрый алгоритм поиска, который я знаю, - это двоичный поиск, который имеет сложность O (log n), поэтому общая сложность будет равна O (log m + log n).
Вот пример, предположим, что мы ищем 28:

 1  2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

Мы выполняем двоичный поиск по элементам первого столбца (1, 11, 21, 31, 41) и обнаруживаем, что строка является третьей, поскольку ее первый элемент меньше нашего числа, но следующий первый элемент первой строки больше. Количество шагов: 2 (21, 31, найдено)
Мы повторяем двойной поиск по третьей строке (21, 22, 23, 24, 25, 26, 27, 28, 29, 30) и находим наш номер. Количество шагов: 2 - 3 (25, 27 или 28, найдено)

Ответ 5

Я думаю, что это можно сделать в O (log (n * n) * log (n)) времени, где n - нет. строк квадратной матрицы.

По свойствам матрицы, главной диагональю матрицы является отсортированный массив. Итак, мы можем искать элемент или его нижнюю границу в O (log (n)). Теперь, используя этот элемент как ось вращения, мы имеем 4 подматрицы. и мы можем сказать, что все элементы в подматрице (слева вверху) меньше, все элементы в подматрице (справа внизу) больше. Таким образом, мы можем удалить это из пространства поиска.

Теперь, рекурсивный поиск в подматрице (вверху справа) и в подматрице (внизу слева).

Так как на каждом шаге мы выполняем log (n) поиск (по главной диагонали) ad, могут быть самые низкие шаги log (n * n) (поскольку мы уменьшаем пространство поиска пополам на каждом шаге).

Итак, сложность времени = O (log (n) log (nn)).

Пожалуйста, исправьте, если что-то не так.

Рефенции - [Книга] Взламывание интервью с кодированием (вопрос 11.6)