[Tutor] Binary search question

Alan Gauld alan.gauld at btinternet.com
Sat Apr 24 01:41:05 CEST 2010

"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
>>> -5 in data

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
>>> "-5" in data

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

More information about the Tutor mailing list