Простая задача и известный алгоритм:
У меня есть большой массив из 100 элементов. Первые X членов равны 0, а остальные 1. Найдите X.
Я решаю это с помощью бинарного поиска: проверить элемент 50, если он равен 0, проверить элемент 75 и т. д., пока не найду соседние 0 и 1.
Я ищу оптимизированный алгоритм для решения той же задачи в двух измерениях:
У меня есть двумерный массив 100*100. Те элементы, которые находятся в строках 0-X И в столбцах 0-Y равны 0, а остальные равны 1. Как найти Y и X?
Простое решение: двигаться сначала в направлении X, а затем в направлении Y.
Чек (0,50); Если это 0, проверьте (0,75); пока не найдете соседние 0 и 1. Затем идите оттуда в направлении Y.
Второе решение:
Проверьте член (50,50). Если это 1, проверяйте (25,25), пока не найдете 0. Продолжайте, пока не найдете соседние (X,X) и (X+1,X+1), которые равны 0 и 1. Затем проверьте (X,X +1) и (Х+1,Х). Ни один, ни один из них не будет 1. Если ни то, ни другое, вам конец. Если только один, например (X+1,X), то Вы знаете, что размер коробки находится между (X+1,X) и (100,X). Используйте бинарный поиск, чтобы найти высоту коробки.
РЕДАКТИРОВАНИЕ. Как заметил Крис, кажется, что простой подход работает быстрее.
Второе решение (модифицированное):
Проверьте член (50,50). Если это 1, проверяйте (25,25), пока не найдете 0. Продолжайте, пока не найдете соседние (X,X) и (X+1,X+1), которые равны 0 и 1. Затем проверьте (X,X +1). Если это 1, то выполните двоичный поиск в строке (X, X + 1)... (X, 100). В противном случае выполните двоичный поиск в строке (X, X)... (100, X).
Даже тогда я, вероятно, бью здесь дохлую лошадь. Если и будет быстрее, то на ничтожно малую величину. Это чисто теоретическое развлечение. :)
РЕДАКТИРОВАНИЕ 2 Как выразились Фезвез и Крис, бинарный поиск наиболее эффективно делит область поиска на две части; Мой подход делит площадь на 1/4 и 3/4 части. Фезвес указал, что это можно исправить, предварительно рассчитав коэффициент деления (но это будет дополнительный расчет). В модифицированной версии моего алгоритма я выбираю направление, куда идти (направление X или Y), что также эффективно делит пространство поиска на две части, а затем провожу бинарный поиск. В заключение, это показывает, что этот подход всегда будет немного медленнее. (и сложнее в реализации).
Спасибо, Игорь Окс, за интересный вопрос. :)
Редактировать: оптимальное решение состоит из двух простых бинарных поисков.
Я очень извиняюсь за длинный и запутанный пост, который я сделал ниже. В чем суть проблемы, так это в том, чтобы найти точку в пространстве, содержащем 100*100 элементов. Лучшее, что вы можете сделать, это разделить на каждом шаге это пространство пополам. Вы можете сделать это запутанным способом (тот, который я сделал в остальной части поста). Но если вы понимаете, что бинарный поиск по оси X по-прежнему делит пространство исследования на два на каждом шаге (то же самое касается Y оси) то вы понимаете что это оптимально.
Я все еще позволяю тому, что я сделал, и мне жаль, что я сделал несколько безапелляционных утверждений.
Если вам нужен простой алгоритм (хотя и не оптимальный), просто запустите двоичный поиск дважды, как это предлагается.
Однако, если вам нужен оптимальный алгоритм, вы можете одновременно искать границу на X и на Y. (Вы должны отметить, что два алгоритма имеют одинаковую асимптотическую сложность, но оптимальный алгоритм все равно будет быстрее)
На всех следующих рисунках точка (0, 0) находится в левом нижнем углу.
По сути, когда вы выбираете точку и получаете результат, вы делите свое пространство на две части. Когда вы думаете об этом, это на самом деле самый большой объем информации, который вы можете извлечь из этого.
Если вы выбираете точку (черный крест) и результат равен 1 (красные линии), это означает, что искомая точка не может находиться в сером поле (таким образом, она должна находиться в оставшаяся белая область)
С другой стороны, если значение равно 0 (синие линии), это означает, что искомая точка не может находиться в серой области (таким образом, она должна находиться в оставшейся белой области).
Итак, если вы получите один результат 0 и один результат 1, вы получите следующее:
Точка, которую вы ищете, находится в прямоугольнике 1, 2 или 3. Вам просто нужно проверить два угла прямоугольника 3, чтобы узнать, какой из 3 прямоугольников является хорошим.
Итак, алгоритм следующий:
Обратите внимание, где находятся нижний левый и верхний правый углы прямоугольника, с которым вы работаете.
Выполняйте двоичный поиск по диагонали прямоугольника, пока не наткнетесь хотя бы один раз на результат 1 и один раз на результат 0.
Проверьте 2 других угла прямоугольника 3 (вам необходимо уже знать значения двух углов по диагонали). Можно проверить только один угол, чтобы узнать правильный прямоугольник (но вам нужно будет проверить два угла). если правый прямоугольник является прямоугольником 3)
Определите, находится ли искомая точка в прямоугольнике 1, 2 или 3
Повторяйте, уменьшая задачу до правильного прямоугольника, пока последний прямоугольник не уменьшится до точки: это значение, которое вы ищете.
Редактировать: если вам нужна оптимальная оптимальность, вы бы не выбрали точку (50, 50), вы не разрезаете пространство на равные части. Один в три раза больше другого. В идеале вы должны выбрать точку, которая делит пространство на две равные области (по площади).
Вы должны вычислить один раз в начале значение factor = (1.0 - 1.0/sqrt(2.0)). Затем, когда вы хотите разрезать между значениями a и b, выберите точку разреза как a + factor*(b-a). Когда вы разрезаете первоначальный прямоугольник 100x100 в точке (100*фактор, 100*фактор), две области будут иметь площадь (100*100)/2, поэтому сходимость будет быстрее.
Запустите бинарный поиск дважды. Сначала определите X, запустив двоичный поиск в последней строке, а затем определите Y, запустив двоичный поиск в последнем столбце.
Используйте бинарный поиск для обоих измерений и случая 1D:
