
function bisect(v, x, imin::Int, imax::Int)
    # https://docs.python.org/2/library/bisect.html
    # The returned insertion point i partitions the sorted vector v into two halves so that 
    # all(val <= x for val in v[1:i]) for the left side and
    # all(val > x  for val in v[i:hi]) for the right side.
    if imin == imax
        x <= v[imin] ? imin : imin + 1
    else
        imid = div(imin+imax, 2)
        if x == v[imid]
            return imid
        elseif x > v[imid]
            bisect(v, x, imid + 1, imax)
        else
            bisect(v, x, imin, max(imid - 1, imin))
        end
    end 
end
function bisect(v, x)
    bisect(v,x,1,length(v))
end 

function genSamples(values, weights::Vector{Float64}, n::Int64)
    @assert length(values) == length(weights)
    if sum(weights) == 1.0
        probs = weights
    else 
        probs = weights/sum(weights)
    end 
    cdf = cumsum(probs)
    samples = []
    for i in 1:n
        u   = rand()
        i   = bisect(cdf, u)
        push!(samples, values[i])
    end 
    return samples
end