[Tutor] Binary search question

[Alan Gauld]

"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
sets.

> 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
http://www.alan-g.me.uk/