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

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

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

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

история

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

  • Дэвид Грис, «Наука программирования» . Springer-Verlag, 1989 .
  • Эдсгар Дейкстра, Поиск Saddleback. Примечание 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) , которую Bird показывает как 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) «seddleback» намного проще, но страдает от ухудшения производительности, поскольку массивы становятся все более прямоугольными ,

Эта проблема занимает время Θ(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 . Для устранения есть длинные строки. Устранение длинной строки требует времени O(lg(t)) . Устранение t коротких столбцов стоит O(1) раз.

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

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

Код

 public static Tuple TryFindItemInSortedMatrix(this IReadOnlyList> grid, T item, IComparer comparer = null) { if (grid == null) throw new ArgumentNullException("grid"); comparer = comparer ?? Comparer.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; } 

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

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

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

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

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

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

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

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

 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) «ZigZag» и метод двоичного поиска 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. Сортировка косвенно, так как я фактически не нахожу номер, я просто выводю, что он должен быть там. У этого есть дополнительный бонус подсчета ВСЕХ 3-х.

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

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

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

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

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

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

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

 1 2 3 2 3 4 3 4 5 

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

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

Скажем, я ищу, например, 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, который хранит данные в строчном порядке, просто обрабатывайте его как 1D-массив размером n * m и используйте двоичный поиск.

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

IF N == LU и N == RB :::: Element Found и Abort возвращают позицию / индекс. Если N> = LU и N <= RB = FALSE, то нет и не выполняется. Если N> = LU и N <= RB = TRUE, разделите 2D-массив в 4 равных частях 2D-массива каждый логически. И затем примените тот же шаг алгоритма ко всем четырем подматрицам.

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

Я думаю, что что-то не так где-то в моем вычислении Сложности, пожалуйста, исправьте, если это так ..

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

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

Страtagsя 1:

  1. Переместитесь в колонку и найдите данный элемент, пока мы не достигнем конца. Если найдено, return найдено как true
  2. Двигайтесь влево в строке и ищите данный элемент, пока мы не достигнем конца. Если найдено, return найдено как true
  3. return найдено как false

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

  • Повторите шаги ниже, пока ik> = 0
    1. Найдите, если [ik] [j] равен данному элементу. если да, возврат найден как истинный.
    2. Найдите, если значение [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 ? 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  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 ++.

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

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

 [abc]
 [def]
 [ijk]

Мы знаем, что 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) Check row 3. q < k? (no, go next)

There is probably a better solution out there but this is easy to explain.. 🙂

As this is an interview question, it would seem to lead towards a discussion of Parallel programming and Map-reduce algorithms.

See http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html

  • Как построить BST при постоперационном обходе
  • Обосновать текст в Android-приложении, используя WebView, но представляя интерфейс TextView?
  • Быстрый алгоритм быстрого поиска диапазона, в котором содержится номер в наборе диапазонов?
  • Как я могу манипулировать значимостью поиска полнотекстового поиска MySQL, чтобы сделать одно поле более «ценным», чем другое?
  • В чем разница между re.search и re.match?
  • Стилизация SearchView в панели действий Android
  • Поиск массивов «не найден», даже если он найден
  • как рассчитать сложность двоичного поиска
  • Откат в звезде
  • Найти все элементы на странице, чей идентификатор элемента содержит определенный текст, используя jQuery
  • Поиск всех возможных комбинаций чисел для достижения заданной суммы
  • Давайте будем гением компьютера.