Ортогональный поиск

Простейший случай

Пусть дана прямая с точками на ней и отрезок. Точки даны в отсортированном порядке. Необходимо указать, какие из изначальных точек лежат на этом отрезке.

Данная задача решается с помощью функций из STL - upper_bound и lower_bound.

upper_bound возвращает наименьшее значение больше данного, lower_bound - наибольшее значение меньше данного.

Рассмотрим на примере:

Код реализации:

template<class RauIter, class OutIter, class Scalar> OutIter range_search(RauIter p, RauIter q, OutIter out)
{
   return std::copy(lower_bound(p, q, l), upper_bound(p, q, r), out);
}

Сбалансированное дерево поиска

Переходим к двумерному случаю. Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.

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

В каждом узле будем хранить точки, которые входят в его поддерево.

Теперь для ответа нам нужно спуститься отрезком по дереву и, если все поддерево лежит в отрезке, сразу выдавать его, если нет - спускаться дальше.