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

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))) ).

Это невозможно сделать лучше, чем 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 может быть в любой строке. (Доказательство не является полным, но вот идея)

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

 A|B --- C|D 

все элементы в A меньше 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 ) 

Поскольку строки и столбцы отсортированы, если мы посмотрим на первый элемент каждой строки, мы можем найти, какой из них содержит число, которое мы ищем. Тогда, опять же, мы можем использовать тот факт, что элементы в каждой строке сортируются и находят это число.
Самый быстрый алгоритм поиска, который я знаю, – это двоичный поиск, который имеет сложность 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, найдено)

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

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

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

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

Итак, Time complex = O (log (n) log (n n)).

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

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