[Tutor] Binary search question

Alan Gauld alan.gauld at btinternet.com
Sat Apr 24 10:48:20 CEST 2010

"Steven D'Aprano" <steve at pearwood.info> wrote

>> Interestingly on my PC with Python 3.1:
>> >>> data = list(range(10000000))
>> >>> 9999999 in data
>> takes an apparently constant, sub second time.
> With respect Alan, timing operations by eye is pretty lame, what did you
> do, count your heartbeats? :)

Sure, but I was surprised at the previous post claiming 7 seconds.
I just wanted to show that 'in' should not be discarded too quickly,
its "good enough" for the vast majority of cases even with big data

> I would expect that the difference between searching for 9999999 and -5
> would be insignificant, because in both cases you have to walk the
> entire list. And sure enough, both take about half a second on my PC:

Yes, I did try other values too, but by the "heartbeat test" (you should patent 
it! :-)
they were all 'constant' time.

Alan Gauld
Author of the Learn to Program web site

More information about the Tutor mailing list