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

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

Скажем, мне дан 2-мерный массив, в котором все числа в массиве расположены в порядке возрастания слева направо и сверху вниз.

Как лучше всего искать и определять, есть ли в массиве целевое число?

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

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

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

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

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

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

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

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

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

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

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

История

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

• Дэвид Грис, Наука программирования . Спрингер-Верлаг, 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 - это хорошо, но насколько хорошо эти подходы работают на практике? На приведенной ниже диаграмме рассматриваются четыре алгоритма для все более «квадратных» массивов:

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

Некоторые примечательные моменты:

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

Резюме

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

Эта проблема требует Θ(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;
}

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

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

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

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

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

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

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

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

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

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

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

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

Вот код 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");
    }
}

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

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

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

Конечно, это распространяется и на более крупные массивы. Значит, этот ответ оптимален.

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

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

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));
    }
}

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

Если в вашем примере я ищу 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. В некотором роде косвенный, поскольку я на самом деле не нахожу число, я просто делаю вывод, что он должен быть там. Это имеет дополнительный бонус в виде подсчета ВСЕХ троек.

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

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

A. Выполните двоичный поиск в тех строках, где может находиться целевой номер.

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

Бинарный поиск был бы лучшим подходом, имо. Начиная с 1/2 x, 1/2 y разрезает его пополам. IE квадрат 5x5 будет выглядеть примерно так: x == 2 / y == 3. Я округлил одно значение в меньшую сторону и одно значение в большую сторону, чтобы получить лучшую зону в направлении целевого значения.

Для ясности следующая итерация даст вам что-то вроде x == 1 / y == 2 OR x == 3 / y == 5

Что ж, для начала предположим, что мы используем квадрат.

1 2 3
2 3 4
3 4 5

1. Поиск в квадрате

Я бы использовал бинарный поиск по диагонали. Цель состоит в том, чтобы найти меньшее число, которое не строго ниже целевого числа.

Скажем, я ищу, 4например, тогда я бы остановился 5на (2,2).

Тогда, я уверен , что если 4в таблице, находится в положении либо (x,2)или (2,x)с xв [0,2]. Ну, это всего лишь 2 бинарных поиска.

Сложность не пугает: O(log(N))(3 бинарных поиска по диапазонам длины N)

2. Поиск в прямоугольнике, наивный подход

Конечно, это становится немного сложнее, когда Nи Mотличается (с прямоугольником), рассмотрим этот вырожденный случай:

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17

И, допустим, ищу 9... Диагональный подход все еще хорош, но определение диагонали меняется. Вот моя диагональ [1, (5 or 6), 17]. Допустим, я взял [1,5,17], тогда я знаю, что если 9есть в таблице, то либо в подчасти:

            5  6  7  8
            6  7  8  9
10 11 12 13 14 15 16

Это дает нам 2 прямоугольника:

5 6 7 8    10 11 12 13 14 15 16
6 7 8 9

Итак, мы можем вернуться! возможно, начиная с той, у которой меньше элементов (хотя в данном случае это нас убивает).

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

• Применить бинарный поиск 10 11 12 13 14 15 16, не найдено
• Применить бинарный поиск 5 6 7 8, не найдено
• Применить бинарный поиск 6 7 8 9, не найдено

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

3. Поиск в прямоугольнике, жестокий подход

Было бы намного проще, если бы мы имели дело с квадратом ... так что давайте просто возведем в квадрат.

1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17
17 .  .  .  .  .  .  17
.                    .
.                    .
.                    .
17 .  .  .  .  .  .  17

Теперь у нас есть квадрат.

Конечно, мы, вероятно, НЕ будем создавать эти строки, мы могли бы просто имитировать их.

def get(x,y):
  if x < N and y < M: return table[x][y]
  else: return table[N-1][M-1]            # the max

поэтому он ведет себя как квадрат, не занимая больше памяти (за счет скорости, вероятно, в зависимости от кеша ... да ладно: p)

РЕДАКТИРОВАТЬ:

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

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

У меня есть рекурсивное решение Divide & Conquer. Основная идея для одного шага: мы знаем, что левый верхний (LU) самый маленький, а правый нижний (RB) - самый большой номер, поэтому данный номер (N) должен: N> = LU и N <= РБ

IF N == LU и N == RB :::: Элемент найден и прерван, возврат позиции / индекса. Если N> = LU и N <= RB = FALSE, No отсутствует и прервать выполнение. Если N> = LU и N <= RB = TRUE, разделите 2D-массив на 4 равные части 2D-массива, каждая логическим образом .. А затем примените тот же шаг алгоритма ко всем четырем подматрицам.

Мой алгоритм верен, я реализовал его на компьютере моих друзей. Сложность: каждые 4 сравнения можно использовать для вывода общего количества элементов до одной четвертой в худшем случае .. Итак, моя сложность составляет 1 + 4 x lg (n) + 4 Но я действительно ожидал, что это будет работать на O (п)

Я думаю, что что-то не так в моих расчетах сложности, исправьте, если да ..

Оптимальное решение - начать с левого верхнего угла, имеющего минимальное значение. Двигайтесь по диагонали вниз вправо, пока не дойдете до элемента, значение которого> = значение данного элемента. Если значение элемента равно значению данного элемента, вернуть найденное значение true.

В противном случае отсюда можно поступить двумя путями.

Стратегия 1:

1. Двигайтесь вверх по столбцу и ищите данный элемент, пока не дойдете до конца. Если найдено, вернуть найденное как истину
2. Двигайтесь влево по строке и ищите данный элемент, пока не дойдете до конца. Если найдено, вернуть найденное как истину
3. возврат найден как ложь

Стратегия 2: Пусть i обозначает индекс строки, а j обозначает индекс столбца диагонального элемента, на котором мы остановились. (Здесь i = j, BTW). Пусть k = 1.

• Повторяйте следующие шаги, пока ik> = 0.
  1. Найдите, совпадает ли [ik] [j] с заданным элементом. если да, вернуть найденное как истина.
  2. Найдите, если a [i] [jk] равно заданному элементу. если да, вернуть найденное как истина.
  3. Приращение k

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

public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){

    // base case for recursion
    if(minX > maxX || minY > maxY)
        return false ;
    // early fails
    // array not properly intialized
    if(arr==null || arr.length==0)
        return false ;
    // arr[0][0]> key return false
    if(arr[minX][minY]>key)
        return false ;
    // arr[maxX][maxY]<key return false
    if(arr[maxX][maxY]<key)
        return false ;
    //int temp1 = minX ;
    //int temp2 = minY ;
    int midX = (minX+maxX)/2 ;
    //if(temp1==midX){midX+=1 ;}
    int midY = (minY+maxY)/2 ;
    //if(temp2==midY){midY+=1 ;}


    // arr[midX][midY] = key ? then value found
    if(arr[midX][midY] == key)
        return true ;
    // alas ! i have to keep looking

    // arr[midX][midY] < key ? search right quad and bottom matrix ;
    if(arr[midX][midY] < key){
        if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY))
            return true ;
        // search bottom half of matrix
        if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY))
            return true ;
    }
    // arr[midX][midY] > key ? search left quad matrix ;
    else {
         return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1));
    }
    return false ;

}

Я предлагаю хранить все символы в файле 2D list. затем найдите индекс требуемого элемента, если он существует в списке.

Если нет, напечатайте соответствующее сообщение, иначе напечатайте строку и столбец как:

row = (index/total_columns) и column = (index%total_columns -1)

Это потребует только двоичного времени поиска в списке.

Пожалуйста, предложите какие-либо исправления. :)

Если решение O (M log (N)) подходит для массива MxN -

template <size_t n>
struct MN * get(int a[][n], int k, int M, int N){
  struct MN *result = new MN;
  result->m = -1;
  result->n = -1;

  /* Do a binary search on each row since rows (and columns too) are sorted. */
  for(int i = 0; i < M; i++){
    int lo = 0; int hi = N - 1;
    while(lo <= hi){
      int mid = lo + (hi-lo)/2;
      if(k < a[i][mid]) hi = mid - 1;
      else if (k > a[i][mid]) lo = mid + 1;
      else{
        result->m = i;
        result->n = mid;
        return result;
      }
    }
  }
  return result;
}

Рабочая демонстрация C ++.

Пожалуйста, дайте мне знать, если это не сработает или в нем есть ошибка.

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

Мое решение всегда было:

1. Двоичный поиск по средней диагонали, которая представляет собой диагональ, идущую вниз и вправо, содержащую элемент в (rows.count/2, columns.count/2).

2. Если целевой номер найден, верните true.

3. В противном случае будут найдены два числа ( uи v), которые uменьше, чем цель, vбольше, чем цель, и vодно справа и одно вниз от u.

4. Рекурсивный поиск в подматрице справа uи вверху, vа также в подматрице внизу uи слева v.

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

Вот код (вероятно, не очень Swifty) Swift:

import Cocoa

class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        if (matrix.isEmpty || matrix[0].isEmpty) {
            return false
        }

        return _searchMatrix(matrix, 0..<matrix.count, 0..<matrix[0].count, target)
    }

    func _searchMatrix(_ matrix: [[Int]], _ rows: Range<Int>, _ columns: Range<Int>, _ target: Int) -> Bool {
        if (rows.count == 0 || columns.count == 0) {
            return false
        }
        if (rows.count == 1) {
            return _binarySearch(matrix, rows.lowerBound, columns, target, true)
        }
        if (columns.count == 1) {
            return _binarySearch(matrix, columns.lowerBound, rows, target, false)
        }

        var lowerInflection = (-1, -1)
        var upperInflection = (Int.max, Int.max)
        var currentRows = rows
        var currentColumns = columns
        while (currentRows.count > 0 && currentColumns.count > 0 && upperInflection.0 > lowerInflection.0+1) {
            let rowMidpoint = (currentRows.upperBound + currentRows.lowerBound) / 2
            let columnMidpoint = (currentColumns.upperBound + currentColumns.lowerBound) / 2
            let value = matrix[rowMidpoint][columnMidpoint]
            if (value == target) {
                return true
            }

            if (value > target) {
                upperInflection = (rowMidpoint, columnMidpoint)
                currentRows = currentRows.lowerBound..<rowMidpoint
                currentColumns = currentColumns.lowerBound..<columnMidpoint
            } else {
                lowerInflection = (rowMidpoint, columnMidpoint)
                currentRows = rowMidpoint+1..<currentRows.upperBound
                currentColumns = columnMidpoint+1..<currentColumns.upperBound
            }
        }
        if (lowerInflection.0 == -1) {
            lowerInflection = (upperInflection.0-1, upperInflection.1-1)
        } else if (upperInflection.0 == Int.max) {
            upperInflection = (lowerInflection.0+1, lowerInflection.1+1)
        }

        return _searchMatrix(matrix, rows.lowerBound..<lowerInflection.0+1, upperInflection.1..<columns.upperBound, target) || _searchMatrix(matrix, upperInflection.0..<rows.upperBound, columns.lowerBound..<lowerInflection.1+1, target)
    }

    func _binarySearch(_ matrix: [[Int]], _ rowOrColumn: Int, _ range: Range<Int>, _ target: Int, _ searchRow : Bool) -> Bool {
        if (range.isEmpty) {
            return false
        }

        let midpoint = (range.upperBound + range.lowerBound) / 2
        let value = (searchRow ? matrix[rowOrColumn][midpoint] : matrix[midpoint][rowOrColumn])
        if (value == target) {
            return true
        }

        if (value > target) {
            return _binarySearch(matrix, rowOrColumn, range.lowerBound..<midpoint, target, searchRow)
        } else {
            return _binarySearch(matrix, rowOrColumn, midpoint+1..<range.upperBound, target, searchRow)
        }
    }
}

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

[abc]
[def]
[ijk]

Мы знаем, что a <c, d <f, i <k. Мы не знаем, d <c или d> c и т. Д. У нас есть гарантии только в одномерном измерении.

Глядя на конечные элементы (c, f, k), мы можем сделать своего рода фильтр: N <c? поиск (): следующий (). Таким образом, у нас есть n итераций по строкам, причем каждая строка принимает либо O (log (n)) для двоичного поиска, либо O (1), если отфильтровано.

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

1) Проверьте строку 1. j <c? (нет, иди дальше)

2) Проверьте строку 2. j <f? (да, поиск по корзине ничего не дает)

3) Проверьте строку 3. j <k? (да, поиск по корзине находит это)

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

1) Проверьте строку 1. q <c? (нет, иди дальше)

2) Проверьте строку 2. q <f? (нет, иди дальше)

3) Проверьте строку 3. q <k? (нет, иди дальше)

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

Поскольку это вопрос собеседования, он, кажется, ведет к обсуждению параллельного программирования и алгоритмов уменьшения карты .

См. Http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html.