using StatsBase
pf = StatsBase.Weights(rand(10))
e = sample(pf)

Upon using @which sample(pf), one gets sample(wv::StatsBase.AbstractWeights) in StatsBase at .../StatsBase/src/sampling.jl:425

for which the algorithm is super straightforward. For example, if t in this algorithm is very close to sum(wv), I would say it is better to go over wv starting from the end.

Hence my question, is it possible to do something like a binary search (like searchsorted) to do the same as StatsBase.sample?

If all you have is a vector of relative weights, then you need to do at least some sort of O(n) preprocessing (since you have no idea where the weight is).

If there is some way that you could get the cumulative weights cheaply (i.e. cheaper than cpf = cumsum(pf), which is also O(n)), then you could do: