Это как раз тот кейс, когда выскочили на один из следующих месяцев.

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

пусть на месяц приходится (в среднем) М записей.

тогда если обходить подневно, то на один месяц будет М проверок.

если применить мою оптимизацию однократно, то будет M^(1/2) больших прыжков длиной M^(1/2), и один неудачный отрезок тоже длиной M^(1/2), который идем по дням.
итого 2 * M^(1/2) проверок.

но можно пойти дальше и сделать 3 "слоя": на первом прыгать через M^(2/3), на втором - через M^(1/3) внутри неудачного отрезка.
итого выходит уже 3 * M^(1/3) проверок, то есть при М = 1000000 всего 300 проверок на месяц. Недурственно.

Ну и конечно, если месяцев совсем мало, можно просто найти их границы двоичным поиском.