Бинарный поиск в “массиве отрезков”

228

26 апреля 2017, 12:38

Задан упроядоченый vector из double, где каждый элемент представляет собой конец отрезка. Например, {1,3,5,6,9} -- означает, что существуют следующие отрезки: [1;3], [3;5], [5;6], [6;9]. Массив вектор заранее отсортирован. Требуется для некоторого числа x найти индекс элемента начала отрезка, к которому принадлежит x. Как реализовать такой поиск (здесь ведь ищется не совпадение элемента, а принадлежность числа к диапазону)?

Answer 1

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

x меньше самого первого элемента. за пределами
x больше самого последнего - за пределами.
x равно самому первому элементу. нужно подумать.
x равно самому последнему элементу. нужно подумать.
x находиться в диапазоне первого-последнего и при этом равен одному с элементов.
x находиться в диапазоне первого-последнего и при этом не равен одному с элементов.

поэтому, алгоритм такой. Проверяем на вхождения в диапазон первый-последний и отсекаем первые 4 варианта. Потом применяем обычный бинарный поиск std::lower_bound и std::upper_bound. Если они равны - 5 случай. Если не равны - знаем границы (итераторами). std::distance поможет найти расстояние от начала (то есть, индекс).

На самом деле там нужен только один std::lower_bound + одно сравнение. Но для красоты объяснения было написано по другом.

Answer 2

Дополню ответ KoVadim небольшим кодом

std::vector<unsigned int> v = {1,3,5,7,9};
int to_find = 6;
auto it = std::upper_bound(v.begin(), v.end(), to_find);
int begin = *std::prev(it);
int last = *it;