Нахождение элемента в частично отсортированном массиве

Question

У меня был следующий вопрос на собеседовании.

Существует массив элементов nxn.Массив частично отсортирован, т.е. самый большой элемент в строке i меньше, чем самый маленький элемент в строке i+1.Как вы можете найти данный элемент со сложностью O (n)

Вот мой взгляд на это:

Вы должны перейти к строке n / 2. И начать сравнение, например, вы ищете100 и первое число, которое вы видите, это 110, так что вы знаете, что оно находится либо в этом ряду, либо в строках выше, теперь вы идете n / 4 и т. Д.не так ли O (n * log n) всего?Он должен анализировать каждую строку, которую он достигает, при бинарном поиске, поэтому количество линейных поисков умножается на количество строк, которые ему придется сканировать в среднем.- Мартин Матисяк 5 минут назад.

Я не уверен, что это правильное решение.У кого-нибудь есть что-нибудь получше

Answer 1

Ваше решение действительно занимает O(n log n) при условии, что вы просматриваете каждую строку, которую анализируете. Если вы не будете искать каждую строку, вы не сможете точно выполнить двоичный шаг.

O(n) решение:

Выберите строку n/2, вместо поиска по всей строке, мы просто берем первый элемент предыдущей строки и первый элемент следующей строки. O(1).
Мы знаем, что все элементы строки n/2 должны находиться между этими выбранными значениями (это ключевое наблюдение). Если наше целевое значение находится в интервале, ищите все три строки (3*O(n) = O(n)).

Если наше значение находится за пределами этого диапазона, продолжайте в режиме двоичного поиска, выбрав n/4, если наше значение меньше диапазона, и 3n/4, если значение было больше, и снова сравните с одним элементом соседние ряды.

Поиск правильного блока из 3 строк будет стоить O(1) * O(log n), а поиск элемента будет стоить O(n).

Всего O(log n) + O(n) = O(n).

Answer 2

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

void search(int n[][], int el) {
    int minrow = 0, maxrow;
    while (minrow < n.length && el >= n[minrow][0])
        ++minrow;
    minrow = Math.max(0, minrow - 1);
    maxrow = Math.min(n.length - 1, minrow + 1);
    for (int row = minrow; row <= maxrow; ++row) {
        for (int col = 0; col < n[row].length; ++col) {
            if (n[row][col] == el) {
                System.out.printf("found at %d,%d\n", row, col);
            }
        }
    }
}