Built-in binary search for sorted collections

General Usage
1

Given integers N and k, I’d like to elegantly find the largest integer n for which binomial(n,k) <= N. A way to do this is

function max_n_binom_leq(N::Integer, k::Integer) 
    return maximum(n for n=k:N if binomial(big(n),k) ≤ N) 
end

This is wasteful. because it has complexity O(N) instead of O(log N). The function n -> binomial(big(n),k) is strictly increasing. A better way is to do bisection (binary search). But I wish to avoid implementing it on my own. Does Julia have some built-in methods to solve this elegantly? I would especially like to avoid allocating the whole array k:N, since N might be very large, like typemax(UInt128).

2

searchsortedlast

Something like searchsortedlast(k:N,N,by=n->binomial(big(n),k)) + (k-1)

3

You don’t really have to search much to find this. Even with a very crude approximation like

binomial(n, k) = n * (n - 1) * ... * (n - (k - 1)) / k! ≈ (n - (k - 1) / 2)^k / k!

you can solve for n in closed form and end up somewhere close. With better approximations you can probably get spot on.