Как мне найти номер в 2d массиве, отсортированном слева направо и сверху вниз?

Question

Мне недавно дали этот вопрос на собеседовании, и мне любопытно, каким будет хорошее решение.

Скажем, мне дали 2d массив, где все числа в массиве увеличиваются порядок слева направо и сверху Дно.

Каков наилучший способ поиска и определить, находится ли целевое число в массив

Теперь я хочу использовать бинарный поиск, так как мои данные отсортированы. Я могу определить, находится ли число в одной строке за O (log N) времени. Однако, это два направления, которые сбивают меня с толку.

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

У кого-нибудь есть хорошие идеи по решению этой проблемы?

Пример массива:

Сортировка слева направо, сверху вниз.

1  2  4  5  6  
2  3  5  7  8  
4  6  8  9  10  
5  8  9  10 11  

Answer 1

Вот простой подход:

1. Начните с нижнего левого угла.
2. Если цель меньше этого значения, она должна быть выше нас, поэтому поднимитесь на 1 .
3. В противном случае мы знаем, что цель не может быть в этомстолбец, поэтому переместить вправо на один .
4. Перейти к 2.

Для массива NxM это выполняется в O(N+M).Я думаю, что было бы трудно сделать лучше.:)

---

Редактировать: Много хорошего обсуждения.Я говорил об общем случае выше;ясно, что если N или M малы, вы можете использовать подход двоичного поиска, чтобы сделать это во время, приближающемся к логарифмическому времени.

Вот некоторые подробности для любопытных:

History

Этот простой алгоритм называется Saddleback Search .Это было вокруг некоторое время, и это оптимально, когда N == M.Некоторые ссылки:

• Дэвид Грис, Наука программирования . Springer-Verlag, 1989 .
• Эдсгар Дейкстра, Поиск в седле . Примечание EWD-934, 1985 .

Однако, когда N < M, интуиция предполагает, что бинарный поиск должен работать лучше, чем O(N+M): например, когда N == 1, чистый двоичный поиск будет выполняться в логарифмическом, а не линейном времени.

Наихудший предел

Ричард Берд исследовал эту интуицию, согласно которой двоичный поиск может улучшить алгоритм Saddleback в статье 2006 года:

• Ричард С. Бёрд, Улучшение поиска в обратном направлении: урок в разработке алгоритмов , в математике конструирования программ, с. 82--89, том 4014, 2006 .

Используя довольно необычную диалоговую технику, Берд показывает нам, что для N <= M эта проблема имеет нижнюю границу Ω(N * log(M/N)).Эта граница имеет смысл, поскольку она дает нам линейную производительность при N == M и логарифмическую производительность при N == 1.

Алгоритмы для прямоугольных массивов

Один подход, использующий строковый двоичный файлпоиск выглядит так:

1. Начните с прямоугольного массива, где N < M.Допустим, N это строки, а M это столбцы.
2. Выполните двоичный поиск в средней строке для value.Если мы найдем его, мы закончим.
3. В противном случае мы нашли соседнюю пару чисел s и g, где s < value < g.
4. Прямоугольник чисел вышеи слева от s меньше value, поэтому мы можем устранить его.
5. Прямоугольник ниже и справа от g больше value, поэтому мы можем устранить его.
6. Переходите к шагу (2) для каждого из двух оставшихся прямоугольников.

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

Это придает алгоритму сложность T(N,M) = log(M) + 2 * T(M/2, N/2), что, как показывает Птица, составляет O(N * log(M/N)).

Другой подход, опубликованный Крейгом Гидни описывает алгоритм, подобный подходу выше: он проверяет строку за раз, используя размер шага M/N.Его анализ показывает, что это также приводит к производительности O(N * log(M/N)).

Сравнение производительности

Анализ Big-O - это хорошо, но насколько хорошо эти подходы работают на практике?В приведенной ниже таблице рассматриваются четыре алгоритма для все более «квадратных» массивов:

(«Наивный» алгоритм просто ищет каждый элемент массива. «Рекурсивный» алгоритм описан выше. «Гибридный» алгоритм представляет собой реализацию алгоритма Гидни . Для каждого размера массива производительность был измерен путем синхронизации каждого алгоритма с фиксированным набором из 1 000 000 случайно сгенерированных массивов.)

Некоторые заметные моменты:

• Как и ожидалось, алгоритмы «двоичного поиска» обеспечивают лучшую производительность для прямоугольных массивов, а алгоритм Saddleback лучше всего работает для квадратных массивов.
• Алгоритм Saddleback работает хуже, чем «наивный» алгоритм для 1-мерных массивов, предположительно потому, что он выполняет несколько сравнений для каждого элемента.
• Падение производительности, которое алгоритмы «двоичного поиска» принимают для квадратных массивов, по-видимому, связано с накладными расходами на выполнение повторных двоичных поисков.

Резюме

Умное использование бинарного поиска может обеспечить производительность O(N * log(M/N) как для прямоугольных, так и для квадратных массивов. Алгоритм O(N + M) «Седло» намного проще, но страдает от снижения производительности, так как массивы становятся все более прямоугольными.

Answer 2

Эта проблема занимает Θ(b lg(t)) время, где b = min(w,h) и t=b/max(w,h). Я обсуждаю решение в этом блоге .

Нижняя граница

Злоумышленник может заставить алгоритм сделать Ω(b lg(t)) запросов, ограничив себя главной диагональю:

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

Обратите внимание, что существует b независимых отсортированных списков размером t, требующих Ω(b lg(t)) запросов для полного исключения.

Алгоритм

1. (Предположим без ограничения общности, что w >= h)
2. Сравните целевой элемент с ячейкой t слева от верхнего правого угла допустимой области.
   • Если элемент ячейки совпадает, вернуть текущую позицию.
   • Если элемент ячейки меньше, чем целевой элемент, удалите оставшиеся t ячеек в строке с помощью двоичного поиска. Если при этом найден соответствующий элемент, вернитесь с его позицией.
   • В противном случае элемент ячейки больше, чем целевой элемент, исключая t короткие столбцы.
3. Если не осталось действительной области, вернуть ошибку
4. Перейти к шагу 2

Поиск предмета:

Определение элемента не существует:

Легенда: белые ячейки - это более мелкие элементы, серые ячейки - более крупные элементы, а зеленая ячейка - равный элемент.

Анализ

Есть b*t короткие столбцы для исключения. Есть b длинных ряда для устранения. Устранение длинного ряда стоит O(lg(t)) времени. Устранение t коротких столбцов стоит O(1) времени.

В худшем случае нам придется исключить каждый столбец и каждую строку, что займет время O(lg(t)*b + b*t*1/t) = O(b lg(t)).

Обратите внимание, что я предполагаю, что lg фиксирует результат выше 1 (т.е. lg(x) = log_2(max(2,x))). Вот почему, когда w=h, что означает t=1, мы получаем ожидаемый предел O(b lg(1)) = O(b) = O(w+h).

Код

public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) {
    if (grid == null) throw new ArgumentNullException("grid");
    comparer = comparer ?? Comparer<T>.Default;

    // check size
    var width = grid.Count;
    if (width == 0) return null;
    var height = grid[0].Count;
    if (height < width) {
        var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
        if (result == null) return null;
        return Tuple.Create(result.Item2, result.Item1);
    }

    // search
    var minCol = 0;
    var maxRow = height - 1;
    var t = height / width;
    while (minCol < width && maxRow >= 0) {
        // query the item in the minimum column, t above the maximum row
        var luckyRow = Math.Max(maxRow - t, 0);
        var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
        if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);

        // did we eliminate t rows from the bottom?
        if (cmpItemVsLucky < 0) {
            maxRow = luckyRow - 1;
            continue;
        }

        // we eliminated most of the current minimum column
        // spend lg(t) time eliminating rest of column
        var minRowInCol = luckyRow + 1;
        var maxRowInCol = maxRow;
        while (minRowInCol <= maxRowInCol) {
            var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
            var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
            if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
            if (cmpItemVsMid > 0) {
                minRowInCol = mid + 1;
            } else {
                maxRowInCol = mid - 1;
                maxRow = mid - 1;
            }
        }

        minCol += 1;
    }

    return null;
}

Answer 3

Я бы использовал стратегию «разделяй и властвуй» для этой проблемы, аналогично тому, что вы предложили, но детали немного другие.

Это будет рекурсивный поиск по поддиапазонам матрицы.

На каждом шаге выбирайте элемент в середине диапазона. Если найденное значение соответствует тому, что вы ищете, значит, все готово.

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

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

И ба-да-бинг, ты нашел это.

Обратите внимание, что каждый рекурсивный вызов имеет дело только с текущим поддиапазоном, но не (например) со ВСЕМИ строками выше текущей позиции. Только те, что в текущем поддиапазоне.

Вот вам псевдокод:

bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)

if (minX == maxX and minY == maxY and arr[minX,minY] != value)
    return false
if (arr[minX,minY] > value) return false;  // Early exits if the value can't be in 
if (arr[maxX,maxY] < value) return false;  // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
    print nextX,nextY
    return true
}
else if (arr[nextX,nextY] < value)
{
    if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
        return true
    return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
    if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
        return true
    reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}

Answer 4

Два основных ответа на данный момент, по-видимому, O(log N) "Метод зигзага" и метод бинарного поиска O(N+M). Я думал, что проведу тестирование, сравнивая два метода с различными настройками. Вот подробности:

Массив представляет собой квадрат N x N в каждом тесте, где N варьируется от 125 до 8000 (самая большая куча, которую может обработать моя JVM). Для каждого размера массива я выбрал случайное место в массиве, чтобы поместить один 2. Затем я поместил 3 везде, где это возможно (справа и снизу от 2), а затем заполнил остальную часть массива 1. Некоторые из более ранних комментаторов, казалось, думали, что этот тип установки даст худшее время выполнения для обоих алгоритмов. Для каждого размера массива я выбрал 100 различных случайных мест для 2 (цель поиска) и провел тест. Я записал среднее время выполнения и наихудшее время выполнения для каждого алгоритма. Поскольку это происходило слишком быстро, чтобы получить хорошие показания мс в Java, и потому что я не доверяю Java nanoTime (), я повторял каждый тест 1000 раз, просто чтобы добавить постоянный коэффициент смещения во все времена. Вот результаты:

Бинарный зигзаг бился в каждом тесте как для среднего, так и для наихудшего времени, однако все они в большей или меньшей степени находятся на порядок друг от друга.

Вот код Java:

public class SearchSortedArray2D {

    static boolean findZigZag(int[][] a, int t) {
        int i = 0;
        int j = a.length - 1;
        while (i <= a.length - 1 && j >= 0) {
            if (a[i][j] == t) return true;
            else if (a[i][j] < t) i++;
            else j--;
        }
        return false;
    }

    static boolean findBinarySearch(int[][] a, int t) {
        return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
    }

    static boolean findBinarySearch(int[][] a, int t,
            int r1, int c1, int r2, int c2) {
        if (r1 > r2 || c1 > c2) return false; 
        if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
        if (a[r1][c1] > t) return false;
        if (a[r2][c2] < t) return false;

        int rm = (r1 + r2) / 2;
        int cm = (c1 + c2) / 2;
        if (a[rm][cm] == t) return true;
        else if (a[rm][cm] > t) {
            boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
            boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
            return (b1 || b2);
        } else {
            boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
            boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
            return (b1 || b2);
        }
    }

    static void randomizeArray(int[][] a, int N) {
        int ri = (int) (Math.random() * N);
        int rj = (int) (Math.random() * N);
        a[ri][rj] = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == ri && j == rj) continue;
                else if (i > ri || j > rj) a[i][j] = 3;
                else a[i][j] = 1;
            }
        }
    }

    public static void main(String[] args) {

        int N = 8000;
        int[][] a = new int[N][N];
        int randoms = 100;
        int repeats = 1000;

        long start, end, duration;
        long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
        long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
        long zigSum = 0, zigAvg;
        long binSum = 0, binAvg;

        for (int k = 0; k < randoms; k++) {
            randomizeArray(a, N);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findZigZag(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            zigSum += duration;
            zigMin = Math.min(zigMin, duration);
            zigMax = Math.max(zigMax, duration);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            binSum += duration;
            binMin = Math.min(binMin, duration);
            binMax = Math.max(binMax, duration);
        }
        zigAvg = zigSum / randoms;
        binAvg = binSum / randoms;

        System.out.println(findZigZag(a, 2) ?
                "Found via zigzag method. " : "ERROR. ");
        //System.out.println("min search time: " + zigMin + "ms");
        System.out.println("max search time: " + zigMax + "ms");
        System.out.println("avg search time: " + zigAvg + "ms");

        System.out.println();

        System.out.println(findBinarySearch(a, 2) ?
                "Found via binary search method. " : "ERROR. ");
        //System.out.println("min search time: " + binMin + "ms");
        System.out.println("max search time: " + binMax + "ms");
        System.out.println("avg search time: " + binAvg + "ms");
    }
}

Answer 5

Это краткое доказательство нижней границы задачи.

Вы не можете сделать это лучше, чем линейное время (с точки зрения размеров массива, а не количества элементов). В приведенном ниже массиве каждый из элементов, помеченных как *, может иметь значение 5 или 6 (независимо от других). Поэтому, если ваше целевое значение равно 6 (или 5), алгоритм должен изучить все из них.

1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10

Конечно, это распространяется и на большие массивы. Это означает, что этот ответ является оптимальным.

Обновление: как отметил Джеффри Л. Уитледж, оно является оптимальным только в качестве асимптотической нижней границы времени выполнения и размера входных данных (рассматривается как одна переменная). Время выполнения, рассматриваемое как функция с двумя переменными в обоих измерениях массива, может быть улучшено.

Answer 6

Я думаю, вот ответ, и он работает для любой сортированной матрицы

bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
    if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
    if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
    if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
    if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;

    int xnew = (xmin + xmax)/2;
    int ynew = (ymin + ymax)/2;

    if (arr[xnew][ynew] == key) return true;
    if (arr[xnew][ynew] < key)
    {
        if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
    } else {
        if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
    }
}

Answer 7

Интересный вопрос. Рассмотрите эту идею - создайте одну границу, где все числа больше, чем ваша цель, и другую, где все числа меньше, чем ваша цель. Если что-то осталось между ними, это ваша цель.

Если я ищу 3 в вашем примере, я читаю по первому ряду, пока не нажму 4, а затем найдите наименьшее соседнее число (включая диагонали) больше 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Теперь я делаю то же самое для тех чисел, которые меньше 3:

1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11

Теперь я спрашиваю, есть ли что-нибудь внутри этих двух границ? Если да, то должно быть 3. Если нет, то нет 3. Вроде косвенного, так как я на самом деле не нахожу число, я просто делаю вывод, что оно должно быть там. Это имеет дополнительный бонус подсчета всех 3-х.

Я пробовал это на некоторых примерах, и похоже, что все в порядке.

Answer 8

Бинарный поиск по диагонали массива - лучший вариант. Мы можем узнать, является ли элемент меньше или равен элементам на диагонали.

Answer 9

Учитывая квадратную матрицу следующим образом:

[ a b c ]
[ d e f ]
[ i j k ]

Мы знаем, что a c и т. Д. У нас есть гарантии только в 1-мерном.

Глядя на конечные элементы (c, f, k), мы можем сделать что-то вроде фильтра: N

Позвольте мне привести пример, где N = j,

1) Проверьте строку 1. j

2) Проверьте строку 2. j

3) Проверьте строку 3. j

Попробуйте еще раз с N = q,

1) Проверьте строку 1. q

2) Проверьте строку 2. q

3) Проверьте строку 3. q

Возможно, есть лучшее решение, но это легко объяснить ..:)

Answer 10

EDIT:

Я неправильно понял вопрос. Как отмечают комментарии, это работает только в более ограниченном случае.

На таком языке, как C, в котором данные хранятся в основном порядке строк, просто обработайте их как одномерный массив размером n * m и используйте двоичный поиск.