[Tutor] Binary search question
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!
Author of the Learn to Program web site
More information about the Tutor