Best search algorithm to find condition within a range

[Ian Kelly]

On Tue, Apr 7, 2015 at 4:55 PM, Steven D'Aprano
<steve+comp.lang.python at pearwood.info> wrote:
> On Wed, 8 Apr 2015 12:32 am, Ian Kelly wrote:
>
>> On average, a random Oracle with a search space of 1000000 will need
>> 1000000 guesses.
>
> Surely on average it will only take 500000 guesses?
>
> Best case is that it gets lucky the first time (1 guess). Worst case is that
> it guesses every wrong answer until there is only one answer it hasn't
> given, which is right (1000000 guesses). I assume that the Oracle is smart
> enough to never repeat a guess.

I didn't make that assumption. With replacement, the mean is 1000000,
per the binomial distribution.