Как я ищу число в 2-м массиве, отсортированном слева направо и от начала до конца?
Мне недавно дали этот вопрос об интервью, и мне любопытно, каково хорошее решение его было бы.
Скажите, что мне дают 2-й массив, где все числа в массиве находятся в увеличивающемся порядке слева направо и от начала до конца.
Что лучший способ состоит в том, чтобы искать и определить, находится ли целевое число в массиве?
Теперь, мой первый наклон состоит в том, чтобы использовать двоичный поиск, так как мои данные отсортированы. Я могу определить, находится ли число в одной строке в O (зарегистрируйте N), время. Однако это - 2 направления, которые отбрасывают меня.
Другое решение я думал, может работать, должен запуститься где-нибудь в середине. Если среднее значение является меньше, чем моя цель, то я могу быть уверен, что это находится в левой квадратной части матрицы с середины. Я затем перемещаюсь по диагонали и проверяю снова, уменьшая размер квадрата, которым цель могла потенциально быть в том, пока я не заточил в на целевом числе.
У кого-либо есть какие-либо хорошие идеи решить эту проблему?
Массив в качестве примера:
Отсортированный слева направо, от начала до конца.
1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11
9 ответов
A. Выполните двоичный поиск в тех строках, где может находиться целевой номер.
Б. Сделайте график: ищите число, всегда выбирая наименьший непосещенный соседний узел и выполняя поиск с возвратом, когда обнаруживается слишком большое число
Дана следующая квадратная матрица:
[ a b c ] [ d e f ] [ i j k ]
Мы знаем, что a
Глядя на конечные элементы (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 Возможно, есть лучшее решение, но это легко объяснить .. :)
Двоичный поиск был бы лучшим подходом, imo. Начиная с 1/2 х, 1/2 y сократит его пополам. IE квадрат 5x5 будет чем-то вроде x == 2 / y == 3 . Я округил одно значение вниз и одно значение до лучшей зоны в направлении целевого значения.
Для ясности следующая итерация даст вам что-то вроде x == 1 / y == 2 OR x == 3 / y == 5
Я бы использовал разделение и Стратегия решения этой проблемы похожа на ту, что вы предложили, но детали немного другие.
Это будет рекурсивный поиск по поддиапазонам матрицы.
На каждом шаге выбирайте элемент в середине диапазона. Если найденное значение - это то, что вы ищете, то все готово.
В противном случае, если найденное значение меньше искомого значения, то вы знаете, что оно не находится в квадранте выше и слева от вашего текущего положения. Поэтому рекурсивно ищите два поддиапазона: все (исключительно) ниже текущей позиции и все (исключительно) справа, что находится в текущей позиции или выше нее.
В противном случае (найденное значение больше искомого) вы знаете, что оно не находится в квадранте ниже и правее вашего текущего положения. Поэтому рекурсивно ищите два поддиапазона: все (исключительно) слева от текущей позиции и все (исключительно) выше текущей позиции, что находится в текущем столбце или столбце справа.
И ба-да-бинг, ты это нашел.
Обратите внимание, что каждый рекурсивный вызов касается только текущего поддиапазона, а не (например) ВСЕХ строк над текущей позицией. Только те, что находятся в текущем поддиапазоне.
Вот вам псевдокод:
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)
}
Вот простой подход:
- Начните с нижнего левого угла.
- Если цель меньше этого значения, она должна быть выше нас, поэтому переместится на единицу вверх .
- В противном случае мы знаем, что цель не может быть в этом столбце, поэтому переместитесь вправо .
- Перейти к 2.
Для массива NxM это выполняется в O (N + M) . Думаю, было бы сложно сделать лучше. :)
Edit: Много хороших обсуждений. Я говорил об общем случае выше; ясно, что если N или M малы, вы можете использовать подход двоичного поиска, чтобы сделать это за время, близкое к логарифмическому.
Вот некоторые подробности для любопытных:
История
Этот простой алгоритм называется Saddleback Search . Он существует некоторое время, и он оптимален, когда N == M . Некоторые ссылки:
- Дэвид Грис, Наука программирования . Springer-Verlag, 1989 .
- Эдсгар Дейкстра, Поиски седловины . Примечание EWD-934, 1985 .
Однако, когда N O (N + M) : Например, когда N = = 1 , чистый двоичный поиск будет выполняться за логарифмическое, а не линейное время.
Оценка наихудшего случая
Ричард Берд исследовал эту интуицию о том, что бинарный поиск может улучшить алгоритм Saddleback, в статье 2006 года:
- Ричард С.Bird, Улучшение поиска Saddleback: Урок в разработке алгоритмов , по математике построения программ, стр. 82-89, том 4014, 2006 .
Используя довольно необычный разговорный прием, Бёрд показывает нам, что для N <= M эта задача имеет нижнюю границу Ω (N * log (M / N)) . Эта оценка имеет смысл, поскольку дает нам линейную производительность, когда N == M , и логарифмическую производительность, когда N == 1 .
Алгоритмы для прямоугольных массивов
Один из подходов, использующий двоичный поиск по строкам, выглядит следующим образом:
- Начните с прямоугольного массива, где
N. Допустим, N- это строки, аM- столбцы. - Выполните двоичный поиск в средней строке
значения. Если мы его найдем, все готово. - В противном случае мы нашли смежную пару чисел
sиg, гдеs <значение. - Прямоугольник чисел сверху и слева от
sменьше, чемзначение, поэтому мы можем его исключить. - Прямоугольник ниже и справа от
gбольше, чемзначение, поэтому мы можем его исключить. - Переходите к шагу (2) для каждого из двух оставшихся прямоугольников.
С точки зрения сложности наихудшего случая, этот алгоритм выполняет log (M) работу, чтобы исключить половину возможных решений, а затем дважды рекурсивно вызывает себя для двух меньших проблем.Нам действительно нужно повторить уменьшенную версию этой log (M) работы для каждой строки, , но если количество строк мало по сравнению с количеством столбцов, то можно исключить все эти столбцы в логарифмическом времени начинают становиться полезными .
Это дает алгоритму сложность T (N, M) = log (M) + 2 * T (M / 2, N / 2) , что Бёрд показывает как O (N * журнал (M / N)) .
Другой подход, опубликованный Крейгом Гидни , описывает алгоритм, аналогичный подходу выше: он проверяет строку за раз, используя размер шага M / N . Его анализ показывает, что это также приводит к производительности O (N * log (M / N)) .
Сравнение производительности
Анализ большого числа - это хорошо и хорошо, но насколько хорошо эти подходы работают на практике? В приведенной ниже таблице исследуются четыре алгоритма для все более «квадратных» массивов:
(«Наивный» алгоритм просто ищет каждый элемент массива. «Рекурсивный» алгоритм описан выше. «Гибридный» алгоритм является реализацией Алгоритм Гидни . Для каждого размера массива производительность измерялась путем хронирования каждого алгоритма по фиксированному набору из 1000000 случайно сгенерированных массивов.)
Некоторые примечательные моменты:
- Как и ожидалось, алгоритмы «двоичного поиска» предлагают лучшая производительность для прямоугольных массивов, а алгоритм Saddleback лучше всего работает с квадратными массивами.
- Алгоритм Saddleback работает хуже, чем «наивный» алгоритм для одномерных массивов, предположительно потому, что он выполняет несколько сравнений по каждому элементу.
- Падение производительности, которое алгоритмы «двоичного поиска» принимают на квадратные массивы, вероятно, связано с накладными расходами на выполнение повторяющихся двоичных поисков.
Резюме
Умное использование двоичного поиска может обеспечить производительность O (N * log (M / N) как для прямоугольных, так и для квадратных массивов. O (N + M) ] алгоритм "седла" намного проще,но страдает от снижения производительности, поскольку массивы становятся все более прямоугольными.
Это краткое доказательство нижней границы задачи.
Вы не можете сделать это лучше, чем линейное время (с точки зрения размеров массива, а не количества элементов). В приведенном ниже массиве каждый из элементов, помеченных как * , может иметь значение 5 или 6 (независимо от других). Поэтому, если ваше целевое значение 6 (или 5), алгоритм должен изучить их все.
1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10
Конечно, это также распространяется на более крупные массивы. Это означает, что этот ответ оптимален.
Обновление: как указал Джеффри Л. Уитледж, он оптимален только как асимптотическая нижняя граница времени выполнения по сравнению с размером входных данных (рассматриваемых как единственная переменная). Время выполнения, рассматриваемое как функция с двумя переменными для обоих измерений массива, может быть улучшено.
Интересный вопрос. Рассмотрите эту идею - создайте одну границу, где все числа больше, чем ваша цель, и другую, где все числа меньше вашей цели. Если что-то осталось между ними, это ваша цель.
Если в вашем примере я ищу 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. Типа косвенного, поскольку я на самом деле не нахожу число, я просто делаю вывод, что оно должно быть там. Это имеет дополнительный бонус в виде подсчета ВСЕХ троек.
Я пробовал это на некоторых примерах, и, похоже, все работает нормально.
Итак, для начала предположим, что мы используем квадрат.
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 или 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 и используйте двоичный поиск.