Best search algorithm to find condition within a range

Steven D'Aprano steve+comp.lang.python at pearwood.info
Wed Apr 8 00:55:19 CEST 2015


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.


-- 
Steven




More information about the Python-list mailing list