algorithm - How to return index of an element with probability of the element's value divided by sum of array -

given array , value k, write function return index of element equals k probability of k/sum(input array). assume there no duplicate number in input array.

for example, if input array 1,4,2,3. function should have following behavior:

return 0 probability 1/10;

return 1 probability 4/10;

return 2 probability 2/10;

return 3 probability 3/10;

question 2: how deal if there duplicates in array?

i thinking binary search find element in array, haven't figured out how connect probability.

edited: suggested, this question similar question. however, solution not expected. looking solution embedded binary search, potentially decreases time complexity.

a good solution given key, how use binary search find first element bigger key in sorted array.

you can make accumulated array input, b[i] = a[0] + a[1] + ... + a[i]. generate random int x between 1 , sum(a), binary search b first element not lesser x.

here's example in python (using python's bisect module, that's essentialy binary search).

import random, bisect, collections  def make_random(a):     s = sum(a)     b = list(a)     in xrange(1, len(b)):         b[i] += b[i-1]     def fn():         r = random.randint(1, s)         return bisect.bisect_left(b, r)     return fn  rnd = make_random([1,4,2,3])  c = collections.counter() in xrange(10000):     c[rnd()]+=1  print c 

the result like:

counter({1: 3960, 3: 3036, 2: 1992, 0: 1012})