[Tutor] Binary search question

[Alan Gauld]

"Emile van Sebille" <emile at fenx.com> wrote

>> For completeness sake, on a 10000 item list, using the in operator
>> takes *in the worst case* around 7 seconds.
> Well on my system checking for the last element of a 100k item list 
> returns true almost upon hitting the enter key.  Surely 7 seconds for a 
> list 1/10th the size is a typo?

Interestingly on my PC with Python 3.1:

>>> data = list(range(10000000))
>>> 9999999 in data
True
>>> -5 in data
False

takes an apparently constant, sub second time.
And the same test on Python 2.5 under cygwin is the same.
Now integers will be easier to deal with than strings but:

>>> data = [str(x) for x in range(100000)]
>>> '9999' in data
True
>>> "-5" in data
False
>>> 

Produces the same results.

And even at 10000000 entries, the list creation slowed right 
down - about 10 seconds, but the searches even for "-5" were 
still around a second.

So 'in' looks pretty effective to me!

-- 
Alan Gauld
Author of the Learn to Program web site
http://www.alan-g.me.uk/