Давайте попробуем искать не первый/последний из эквивалентных элементов, а границы содержащего их интервала.

Интервал будет полуоткрытый справа, т.е. [lower_bound, upper_bound) как и все используемые интервалы. В случае, если искомого элемента нет, интервал будет пустой и обе границы (у пустого интервала границы равны) будут указывать на «место для вставки».

Для определения как отсортирована последовательность используем компаратор.
Будем считать, что компаратор comp в нашей последовательности выполняет роль оператора < и элементы в ней отсортированы по возрастанию (возрастанию относительно компаратора).
Т.е. если у нас последовательность целых чисел отсортирована по убыванию, то компаратором в ней будет оператор >. Если у нас последовательность пар чисел, отсортированных по величине второго числа… ну вы поняли о чем я.

lower_bound — позиция первого элемента, который не меньше искомого.
upper_bound — позиция первого элемента, который больше искомого.

Я буду использовать не индексы, а итераторы т.к. считаю, что в данной постановке задачи они уместнее (а ещё потому, что я это буду делать на C++ «в стиле STL»).

Попробуем найти lower_bound:

template<typename FwdIter, typename T, typename Comp>
FwdIter lower_bound(FwdIter first, FwdIter last, T const& x, Comp comp)
{
    // если интервал пустой, то его и возвращаем
    if (first == last)
        return first;
    
    // вычислим позицию среднего элемента
    FwdIter middle = first;
    std::advance(middle, std::distance(first, last) / 2);
    
    // Если средний элемент меньше искомого, т.е. искомый больше среднего элемента,
    // то т.к. последовательность отсортирована по возрастанию,
    // искомый элемент должен находиться справа от среднего, иначе — слева
    if (comp(*middle, x))
        return lower_bound(++middle, last, x, comp);
    else
        return lower_bound(first, middle, x, comp);
}

upper_bound можно выразить через lower_bound:
У нас есть оператор <, а нам нужен ≤.
Выразим одно через другое:
a ≤ b ⇔ !(b < a)

template<typename FwdIter, typename T, typename Comp>
FwdIter upper_bound(FwdIter first, FwdIter last, T const& x, Comp comp)
{
    typedef typename std::iterator_traits<FwdIter>::value_type value_type;
    
    auto less_equal = [&comp](value_type const& a, T const& b){return !comp(b, a);};
    
    return lower_bound(first,last, x, less_equal);
}

Варианты для компаратора по умолчанию пишутся тривиально.

Ну и осталась обертка для проверки входит ли элемент в последовательность и на какой позиции.

template<typename FwdIter, typename T, typename Comp>
FwdIter binary_search(FwdIter first, FwdIter last, T const& x, Comp comp)
{
    FwdIter found = lower_bound(first, last, x, comp);
   
    // Если элемент не найден, found может оказаться равен правой границе.
    // Если found указывает на существующий элемент, то он не меньше искомого.
    // Т.е. *found или больше или равен x, если больше, то x не нашелся.
    if (found == last || comp(x, *found))
    {
        // Элемент не найден.
        // Вернем верхнюю границу диапазона в качестве индикатора.
        return last;
    }
   
    return found;
}

Последняя обертка, не даёт информацию о месте вставки, если элемент не нашелся, однако никто не запрещает воспользоваться lower_bound напрямую, если мы собираемся вставлять элемент.

За исключеним нескольких нюансов, мы практически переизобрели соответствующие алгоритмы из STL:
lower_bound
upper_bound
binary_search
equal_range

Тщательно не тестировал, но вроде работает.