Здравствуйте коллеги, такая задача
есть отсортированная последовательность типа

0,1,5,6,6,6,6,6,7
нужно за логарифмическое время найти первый элемент равный либо 6 (то есть после 5 — кой) и последний (перед 7 — кой)

я попробовал реализовать так бинарно ищу последний меньший/больший если он не равен искомому ключу то возвращаю его, если но равен ключу, то запускаю снова бинарный "подпоиск" на интервале от начало/конца массива до этого элемента если "под поиск" больше не нашел ключей то возвращаю первое найденное значение иначе повторяю рекурсивно.
Но не нравиться сам реализация с под. поисками, возможно есть другие решения.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте коллеги, такая задача
А>есть отсортированная последовательность типа

А>0,1,5,6,6,6,6,6,7
А>нужно за логарифмическое время найти первый элемент равный либо 6 (то есть после 5 — кой) и последний (перед 7 — кой)

А>я попробовал реализовать так бинарно ищу последний меньший/больший если он не равен искомому ключу то возвращаю его, если но равен ключу, то запускаю снова бинарный "подпоиск" на интервале от начало/конца массива до этого элемента если "под поиск" больше не нашел ключей то возвращаю первое найденное значение иначе повторяю рекурсивно.
А>Но не нравиться сам реализация с под. поисками, возможно есть другие решения.

А ничего и не надо делать
На каждом шаге алгоритма мы должны сузить интервал, так?
Мы взяли какой-то элемент внутри существующего интервала, и если он меньше искомого, то берем правую часть.
А вот если меньше или равен искомому — то левую. Таким образом — если мы попадаем на 6-ку и ищем 6, то всегда будем двигаться к самой левой шестерке, ведь 6 <= 6, а значит мы выбираем левый интервал, пока не дойдем до самой левой 6-ки.

Эх, поднапутал с формулировкой условий.
Если элемент меньше (<) искомого, то берем правую часть (ведь справа все бОльшие).
Если элемент больше или равен искомому (>=), то берем левую часть (ведь слева все меньшие и наши предшествующие дубликат (если они есть)).

В общем, главное правильно выбрать строгое или нестрогое неравенство.

Здравствуйте, Аноним, Вы писали:

А>есть отсортированная последовательность типа
А>0,1,5,6,6,6,6,6,7
А>нужно за логарифмическое время найти первый элемент равный либо 6 (то есть после 5 — кой) и последний (перед 7 — кой)

Это называется lower_bound и upper_bound.

X[k-1] < Q <= X[k] — lower_bound, т.е. всё, что левее (исключая найденную позицию), строго меньше искомого
X[k-1] <= Q < X[k] — upper_bound, т.е. всё, что правее (включая найденную позицию), строго больше искомого

оба алгоритма дихотомические, отличаются лишь условием.

http://en.cppreference.com/w/cpp/algorithm/lower_bound
http://en.cppreference.com/w/cpp/algorithm/upper_bound

Делим интервал примерно пополам (примерно — потому что длина может быть нечётной) и смотрим, какую половину можно смело откинуть.
До тех пор, пока не получим интервал нулевой или единичной длины.

Для оптимизации сначала binary_search можно сначала сделать, и его результат использовать как верхнюю границу для lower_bound и как нижнюю — для upper_bound

M>Для оптимизации сначала binary_search можно сначала сделать, и его результат использовать как верхнюю границу для lower_bound и как нижнюю — для upper_bound

Зачем?

Здравствуйте, Кодт, Вы писали:

А>>есть отсортированная последовательность типа
А>>0,1,5,6,6,6,6,6,7
А>>нужно за логарифмическое время найти первый элемент равный либо 6 (то есть после 5 — кой) и последний (перед 7 — кой)
К>Это называется lower_bound и upper_bound.

Скорее std::equal_range — при заданных условиях, он будет не медленнее, а то и быстрее, чем lower_bound + upper_bound.

К>оба алгоритма дихотомические, отличаются лишь условием.

Если реализовывать вручную, то проще всего начать с std::partition_point, подставив необходимое условие потом.

Здравствуйте, dr. Acula, Вы писали:

DA>Зачем?

binary_search покажет на позицию где-то внутри диапазона

  binary_search
       |
       v
15666666666666777
  ^          ^
  |          |
lower_bound  |
             |
        upper_bound

И при вызовах lower_bound и upper_bound нам надо будет работать с уменьшенным диапазоном. Т.е. у lower_bound и upper_bound первые N шагов будут одинаковы (пока не наткнемся на искомый диапазон), используя binary_search мы убираем дублирование исполнения этих первых N шагов.

Здравствуйте, marat321, Вы писали:

M>И при вызовах lower_bound и upper_bound нам надо будет работать с уменьшенным диапазоном. Т.е. у lower_bound и upper_bound первые N шагов будут одинаковы (пока не наткнемся на искомый диапазон), используя binary_search мы убираем дублирование исполнения этих первых N шагов.

Спичечная экономия, если честно.

В зависимости от ситуации, может оказаться эффективнее найти lower_bound и затем от этой точки — линейно find_if. Это более cache friendly, чем ещё один дихотомический забег. А если дубликатов заведомо немного, то и безо всякой оглядки на кэш будет выигрыш.

Конечно, в общем случае, лучше использовать equal_range, который может быть грамотно специализирован для разных типов коллекций.