Поиск в колоночной упорядоченной матрице в сложности O (n)

У меня есть матрица (n * n), которую все ее столбцы упорядочены в порядке убывания , в то время как строки не упорядочены - Я знаю, что каждое значение в строке меньше всех значений в строках ниже, , но значения внутри строк не сортируются, хотя они все либо меньше, либо идентичны значениям в строке ниже.Поиск в колоночной упорядоченной матрице в сложности O (n)

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

Затем я проверю искомое значение в строке ячейки и в строке выше (если ячейка> search_val) или строка ниже (если ячейка < search_val).

Будет ли это работать? Будет ли он работать и в том случае, если столбец заполнен одинаковыми значениями?

источник

2015-06-05 Ido

Этот вопрос похож на точный дубликат [Учитывая массив 2d, отсортированный по возрастающим порядком слева направо и сверху вниз, лучший способ поиска целевого номера?] (Http://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-growth-order-from-left-to-right-and-top-to-bottom) –

Возьмите эту матрицу (4 * 4): {{10 , 1,3,2}, {10,11,12,13}, {10,21,23,22}, {10,100,45,28}} - это неубывающий порядок столбцов, тогда как строки не заказан. Поиск седла не поможет здесь. – Ido

Я знаю, что каждое значение в строке меньше всех значений в строках ниже

Это означает, что строки упорядочены в порядке возрастания

Так, начиная с вашего определения , упорядочиваются как строки, так и столбцы.

Таким образом, вы можете искать свою Матрицу в виде массива размером n * n. Двоичный поиск в этом случае будет идти:

O(log(n*n)) = O(2*log(n)) = O(log(n)) < O(n)

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

источник

2015-06-05 07:21:27 B3rn475

Предположим, что у меня есть эта матрица (4 * 4): {{10,1,3,2}, {10,11,12,13}, {10,21,23,22}, {10,100,45,28 }} - это неубывающий порядок столбцов, в то время как строки не упорядочены. Скажем, я ищу значение 21. Я могу запустить двоичный поиск по всем столбцам, но он даст мне O (n * logn). – Ido

, а как насчет «всех его столбцов упорядочены в порядке убывания»? – B3rn475

Столбцы не убывают - но строки могут быть неупорядочены, если все значения в одной строке меньше или равны значениям в строке ниже. – Ido

Поиск в колоночной упорядоченной матрице в сложности O (n)

ответ

Смежные вопросы