[Tutor] "bisect" vs "in"

[Peter Otten]

Albert-Jan Roskam wrote:

> I want to repeatedly search a list to test whether that list contains a
> given element X. Of course, I can use membership testing using "in"
> (list._contains__). But how is this method implemented? It seems to just
> walk through the whole list from beginning to end (see timeit code below).

Indeed.

> Is it faster to do a binary search on a sorted list, given that this task
> has to be done repeatedly? 

Much faster. You don't see that in your timings because you include the 
creation of the range(10**7) list in your measurement.

If you used a set instead of a list you could use "in", and it would be even 
faster than bisect.

> Can such a program be scaled to lists that do
> not fit into memory (maybe using shelve?)?

That would slowdown things a lot. Disk access is *much* slower than RAM.