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

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

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

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

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