[OT] Algorithm question

[Ivan Kazmenko via Digitalmars-d]

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.