binsearch

//Есть монотонная функция f, надо найти такое последнее x: f[x] <= k.
left = (такое x, что f(x) <= k)
right = (такое x, что f(x) > k])
while left != right - 1:
    middle = (left + right) / 2;
    if f(middle) <= k):
        left = middle
    else:
        right = middle

//Ответ — в left