On Monday, 1 May 2017 at 21:54:43 UTC, MysticZach wrote:
On Monday, 1 May 2017 at 16:56:58 UTC, MysticZach wrote:
The goal is to have the first hit be the one you return. The
method: if a random pick doesn't satisfy, randomly choose the
partition greater than or less than based on
uniform(0..array.length-1), and do the same procedure on that
partition, reusing the random index to avoid having to call
uniform twice on each recursion (one to choose a partition and
one to choose an index within that partition). If the
probability of choosing a partition is precisely proportional
to the number of elements in that partition, it seems to me
that the result will be truly random, but I'm not sure.
Now I'm questioning this, because if the positive cases are
unevenly distributed, i.e., [111111000100], the last one has
about 50% chance to get picked instead of a 1 in 7 chance with
my method. I guess you'd need to build a whole new array like
the others are saying.
A pity; it sounded nice!
But yeah, once we pick the right ~half, we have to completely
traverse it before paying any attention to the left ~half.
I hope some part of the idea is still salvageable.
For example, what if we put the intervals in a queue instead of a
stack?
Ivan Kazmenko.
