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

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