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