Задан упроядоченый vector из double, где каждый элемент представляет собой конец отрезка. Например, {1,3,5,6,9} -- означает, что существуют следующие отрезки: [1;3], [3;5], [5;6], [6;9]. Массив вектор заранее отсортирован. Требуется для некоторого числа x найти индекс элемента начала отрезка, к которому принадлежит x. Как реализовать такой поиск (здесь ведь ищется не совпадение элемента, а принадлежность числа к диапазону)?
2 ответа
Учитывая, что числа упорядочены и отрезки не перекрываются, достаточно рассмотреть 6 случаев.
- x меньше самого первого элемента. за пределами
- x больше самого последнего - за пределами.
- x равно самому первому элементу. нужно подумать.
- x равно самому последнему элементу. нужно подумать.
- x находиться в диапазоне первого-последнего и при этом равен одному с элементов.
- x находиться в диапазоне первого-последнего и при этом не равен одному с элементов.
поэтому, алгоритм такой. Проверяем на вхождения в диапазон первый-последний и отсекаем первые 4 варианта. Потом применяем обычный бинарный поиск std::lower_bound
и std::upper_bound
. Если они равны - 5 случай. Если не равны - знаем границы (итераторами). std::distance
поможет найти расстояние от начала (то есть, индекс).
На самом деле там нужен только один std::lower_bound
+ одно сравнение. Но для красоты объяснения было написано по другом.
-
Подойдет. Но если это тысяча, то моим способом за 10 сравнений, а линейно циклом - до тысячи. Выгода очевидна.– KoVadim27 апр 2017 в 18:45
-
Дополню ответ 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;