For method 2, if you precompute the cumulative distribution function, you can do a binary search which is only O(log N) instead of O(N).